[LintCode] 611 Knight Shortest Path 解题报告

Description
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


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


Code

/**
 * Definition for a point.
 * public class Point {
 *     publoc int x, y;
 *     public Point() { x = 0; y = 0; }
 *     public Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param grid a chessboard included 0 (false) and 1 (true)
     * @param source, 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 || 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;
    }
}