Number of Moves to Capture the King - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<vector<int>>& nums) {
    int n = nums.size(), m = nums[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (nums[i][j] == 2) {
                dist[i][j] = 0;
                q.push({i, j});
                break;
            }
        }
    }
    if (q.empty()) return -1;

    vector<int> xdir{1, 2, -1, 2, -1, -2, 1, -2};
    vector<int> ydir{2, 1, 2, -1, -2, -1, -2, 1};
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 8; k++) {
            int x = i + xdir[k];
            int y = j + ydir[k];
            if (x >= 0 and x < n and y >= 0 and y < m and nums[x][y] != 2 and
                dist[x][y] > dist[i][j] + 1) {
                if (nums[x][y] == 1) return dist[i][j] + 1;
                dist[x][y] = dist[i][j] + 1;
                q.push({x, y});
            }
        }
    }
    return -1;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    int[] dr = {-1, -1, 1, 1, 2, 2, -2, -2};
    int[] dc = {2, -2, 2, -2, 1, -1, 1, -1};

    public int solve(int[][] board) {
        LinkedList<Pair<Integer, Integer>> q = new LinkedList();
        HashSet<Pair<Integer, Integer>> hs = new HashSet();
        int m = board.length, n = board[0].length;
        int king_r = 0, king_c = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 1) {
                    q.addLast(new Pair(i, j));
                    hs.add(new Pair(i, j));
                } else if (board[i][j] == 2) {
                    king_r = i;
                    king_c = j;
                }
            }
        }
        int moves = 0;
        while (q.size() > 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Pair<Integer, Integer> cur = q.removeFirst();
                int cur_r = cur.getKey(), cur_c = cur.getValue();
                if (cur_r == king_r && cur_c == king_c)
                    return moves;
                for (int move = 0; move < 8; move++) {
                    int new_r = cur_r + dr[move];
                    int new_c = cur_c + dc[move];
                    if (new_r < 0 || new_c < 0 || new_c >= n || new_r >= m)
                        continue;
                    if (hs.contains(new Pair(new_r, new_c)))
                        continue;
                    hs.add(new Pair(new_r, new_c));
                    q.addLast(new Pair(new_r, new_c));
                }
            }
            moves++;
        }
        return -1;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, board):
        r = len(board)
        c = len(board[0])
        dist = []
        for _ in range(r):
            dist.append([r * c + 1] * c)
        q = []
        sx, sy = None, None
        for i in range(r):
            for j in range(c):
                if board[i][j] == 1:
                    q.append((i, j))
                    dist[i][j] = 0
                elif board[i][j] == 2:
                    sx, sy = i, j
        for x, y in q:
            for dx, dy in [(-2, -1), (-2, 1), (-1, 2), (-1, -2), (1, -2), (1, 2), (2, -1), (2, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < r and 0 <= ny < c and dist[nx][ny] > 1 + dist[x][y]:
                    dist[nx][ny] = 1 + dist[x][y]
                    q.append((nx, ny))
        ans = dist[sx][sy]
        if ans > r * c:
            ans = -1
        return ans