611.骑士的最短路线

描述

给定骑士在棋盘上的 初始 位置(一个2进制矩阵 0 表示空 1 表示有障碍物)，找到到达 终点 的最短路线，返回路线的长度。如果骑士不能到达则返回 -1 。

注意事项

起点跟终点必定为空.
骑士不能穿过障碍物.

说明

如果骑士的位置为 (x,y)，他下一步可以到达以下这些位置:

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

样例

[[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

代码

数组是布尔数组，0代表false代表可达点，1代表true代表不可达点

public class Solution {
    int n, m; // size of the chessboard
    // 这是坐标变换数组，在矩形图中用坐标变换数组+for循环来进行图中点的遍历
    int[] deltaX = {1, 1, 2, 2, -1, -1, -2, -2};
    int[] deltaY = {2, -2, 1, -1, 2, -2, 1, -1};
    /**
     * @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) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        n = grid.length;
        m = grid[0].length;
        
        Queue<Point> queue = new LinkedList<>();
        queue.offer(source);
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point point = queue.poll();
                if (point.x == destination.x && point.y == destination.y) {
                    return steps;
                }

                for (int direction = 0; direction < 8; direction++) {
                    Point nextPoint = new Point(
                        point.x + deltaX[direction],
                        point.y + deltaY[direction]
                    );
                    // 不在界内以及标记为true的点跳过
                    if (!inBound(nextPoint, grid)) {
                        continue;
                    }
                    // 界内的且标记为false的点加入队列
                    queue.offer(nextPoint);
                    // 将已经添加到队列的点用true标记
                    grid[nextPoint.x][nextPoint.y] = true;     
                }
            }
            // 每抛出一个点step+1
            steps++;
            
        }
        
        return -1;
    }
    
   
    private boolean inBound(Point point, boolean[][] grid) {
        if (point.x < 0 || point.x >= n) {
            return false;
        }
        if (point.y < 0 || point.y >= m) {
            return false;
        }
        // 判断下一个位置是否有障碍
        return (grid[point.x][point.y] == false);
    }
}