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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

/**  * 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];     } }