Problem statement

https://binarysearch.com/problems/Number-of-Moves-to-Capture-the-King/

Solution

Start bfs from king and traverse until we meet some knight.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def solve(self, board):
        n = len(board)
        for i, j in product(range(n), range(n)):
            if board[i][j] == 2:
                x, y = i, j
        queue = deque([(0, x, y)])
        dirs = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]
        V = set((0, 0))
        
        while queue:
            steps, i, j = queue.popleft()
            if board[i][j] == 1: return steps
            V.add((i, j))
            for dx, dy in dirs:
                if (i + dx, j + dy) in V: continue
                if not 0 <= i + dx < n or not 0 <= j + dy < n: continue
                V.add((i + dx, j + dy))
                queue.append((steps + 1, i + dx, j + dy))

        return -1