Lintcode 611. Knight Shortest Path

Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if destination cannot be reached.

Example

Example 1:

Input:
[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
Output: 2
Explanation:
[2,0]->[0,1]->[2,2]

Example 2:

Input:
[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
Output:-1

Clarification

If the knight is at (x, y), he can get to the following positions in one step:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

Notice

source and destination must be empty.
Knight can not enter the barrier.

Code (Java):

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

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 
     */
    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean[nRows][nCols];
        queue.offer(source);
        visited[source.x][source.y] = true;
        
        int level = 0;
        int[][] dirs = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point curPoint = queue.poll();
                if (curPoint.x == destination.x && curPoint.y == destination.y) {
                    return level;
                }
                
                for (int[] dir : dirs) {
                    int nx = curPoint.x + dir[0];
                    int ny = curPoint.y + dir[1];
                    
                    if (isInBound(grid, nx, ny, visited)) {
                        queue.offer(new Point(nx, ny));
                        visited[nx][ny] = true;
                    }
                }
            }
            
            level++;
        }
        
        return -1;
    }
    
    private boolean isInBound(boolean[][] grid, int x, int y, boolean[][] visited) {
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        return x >= 0 && x < nRows && y >= 0 && y < nCols && !grid[x][y] && !visited[x][y];
    }
}