LintCode - 611 Knight Shortest Path

https://xuezhashuati.blogspot.com/2017/03/lintcode-611-knight-shortest-path.html
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 knight can not reached.

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


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)

Example
[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 2

[[0,1,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 6

[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return -1
http://www.cnblogs.com/EdwardLiu/p/6546118.html
http://www.szeju.com/index.php/other/50222809.html

 6     public static int shortestPath(int[][] board, int[] src, int[] dst) {
 7         int[][] directions = new int[][]{{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
 8         int m = board.length;
 9         int n = board[0].length;
10         int res = 0;
11         
12         Queue<Integer> queue = new LinkedList<Integer>();
13         HashSet<Integer> visited = new HashSet<Integer>();
14         queue.offer(src[0]*n + src[1]);
15         while (!queue.isEmpty()) {
16             int size = queue.size();
17             for (int i=0; i<size; i++) {
18                 int cur = queue.poll();
19                 visited.add(cur);
20                 int x = cur / n;
21                 int y = cur % n;
22                 if (x == dst[0] && y == dst[1]) return res;
23                 
24                 for (int[] dir : directions) {
25                     int nx = x + dir[0];
26                     int ny = y + dir[1];
27                     if (nx<0 || nx>=m || ny<0 || ny>=n || visited.contains(nx*n+ny) || board[nx][ny]!=0)
28                         continue;
29                     queue.offer(nx*n + ny);
30                 }
31             }
32             res++;
33         }
34         return res;
35     }

找最短路径一般都直接上BFS了。没什么特别的思路。硬做。
每个点有8个方向可以走。所以在每一层，要找8个方向，判断一下是否越界，时候已经遍历过。

    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        // Write your code here
        
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return -1;
        }
        
        Queue<Point> queue = new LinkedList<>();
        queue.offer(source);
        
        int[] directionX = new int[] {1, 1, -1, -1, 2, 2, -2, -2};
        int[] directionY = new int[] {2, -2, 2, -2, 1, -1, 1, -1};
        int step = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point pt = queue.poll();
                if (pt.x == destination.x && pt.y == destination.y) {
                    return step;
                }
                for (int j = 0; j < 8; j++) {
                    Point next = new Point(pt.x + directionX[j], pt.y + directionY[j]);
                    if (inBound(grid, next) && !grid[next.x][next.y]) {
                        queue.offer(next);
                        grid[next.x][next.y] = true;
                    }
                }
            }
            step++;
        }
        
        return -1;
    }
    
    public boolean inBound(boolean[][] grid, Point pt) {
        return pt.x >= 0 && pt.x < grid.length && pt.y >= 0 && pt.y < grid[0].length;
    }