Knight Shortest Path

Java

public class Solution {
    /**
     * @param grid: a chessboard included 0 (false) and 1 (true)
     * @param source: a point
     * @param destination: a point
     * @return: the shortest path 
     */
        
        int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
        int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        
        
        Queue<Point> queue = new LinkedList<>();
        boolean[][] v = new boolean [grid.length + 1][grid[0].length + 1];
        queue.offer(source);
        int res =0;
        while(!queue.isEmpty()){
            int size = queue.size(); 
            res++;
            for(int i = 0; i < size; i++){
                Point cur = queue.poll();
                int x = cur.x, y = cur.y;
                
                for(int k = 0; k < 8; k ++){
                    Point nextPoint = new Point(
                    x + dx[k],
                    y + dy[k]);
                    if(nextPoint.x < 0 || nextPoint.x >= grid.length || nextPoint.y<0 || nextPoint.y >= grid[0].length || grid[nextPoint.x][nextPoint.y] || v[nextPoint.x][nextPoint.y]){
                     continue;
                    }  
                    if(nextPoint.x == destination.x && nextPoint.y == destination.y){
                        return res;
                    }
                    queue.offer(nextPoint);
                    v[nextPoint.x][nextPoint.y] = true;
                }
            }
        }
        return -1;
    }
}

Python

class Solution:
    # @param {boolean[][]} grid a chessboard included 0 (False) and 1 (True)
    # @param {Point} source a point
    # @param {Point} destination a point
    # @return {int} the shortest path 
    def shortestPath(self, grid, source, destination):
        # Write your code here
        n = len(grid)
        m = len(grid[0])

        import sys
        record = [[sys.maxsize for _ in range(m)] for i in range(n)]
        record[source.x][source.y] = 0

        import queue
        q = queue.Queue(maxsize = n * m)
        q.put(source)

        d = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]
        while not q.empty():
            head = q.get()
            for dx, dy in d:
                x, y = head.x + dx, head.y + dy
                if x >=0 and x < n and y >= 0 and y < m and not grid[x][y] and \
                    record[head.x][head.y] + 1 < record[x][y]:
                    record[x][y] = record[head.x][head.y] + 1
                    q.put(Point(x, y))

        if record[destination.x][destination.y] == sys.maxsize:
            return -1

        return record[destination.x][destination.y]