Problem

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

思路

• 因为要计算最短距离, 而这个矩阵相当于一个undirected graph, 所以用bfs.
• 每一层相当于下一步的所有可能性, 所以需要层序遍历来记录步数

    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }

        Queue<Point> queue = new LinkedList<>();
        queue.offer(source);
        grid[source.x][source.y] = true;

        int[] deltaX = {1,1,-1,-1,2,2,-2,-2};
        int[] deltaY = {2,-2,2,-2,1,-1,1,-1};

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point curt = queue.poll();
                if (curt.x == destination.x && curt.y == destination.y) {
                    return steps;
                }

                for (int j = 0; j < 8; j++) {
                    Point adj = new Point(curt.x + deltaX[j], curt.y + deltaY[j]);
                    if (adj.x < 0 || adj.y < 0 || adj.x >= grid.length || adj.y >= grid[0].length || grid[adj.x][adj.y]) continue;
                    grid[adj.x][adj.y] = true;
                    queue.offer(adj);
                }
            }
            steps++;
        }

        return -1;
    }