LintCode 题解丨大厂真题：骑士的最短路线

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

起点跟终点必定为空.

骑士不能碰到障碍物.

路径长度指骑士走的步数.

在线评测地址：

LintCode 领扣

​

说明

如果骑士的位置为 (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)

样例

例1:

输入:

[[0,0,0],

[0,0,0],

[0,0,0]]

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

输出: 2

解释:

[2,0]->[0,1]->[2,2]

例2:

[[0,1,0],

[0,0,1],

输出:-1

算法：BFS

朴素​BFS​搜搜最短路，BFS概括来说就是像雷达一样，一层一层进行寻找目标点。当找到目标点后进行回溯。从而找到最佳路径。也就是说每走一步都要找到到达该点的最短的路径，最终得到到达所有点的最短路径，这题每一次的下一步做了规定，按照日字形跳到下一步。

根据下一跳位置建立方向数组

​dx=[1, 1, 2, 2, -1, -1, -2, -2]​

​dy=[2, -2, 1, -1, 2, -2, 1, -1]​

遍历八个方向，进行搜索

用​grid​数组标注是否访问过某点

注意判断下一跳的位置是否越界

复杂度分析

时间复杂度​O(n*m)​

最多跑一边图 n为图的行数，m为图的列数，最多跑一边图，即n*m

空间复杂度​O(n*m)​

所有点的信息 n为图的行数，m为图的列数

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) {
    int n = grid.length,m = grid[0].length;
    if (n == 0 || m == 0) {
        return -1;
    }
    
    int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
    int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
    Queue<Point> queue = new LinkedList<>();
    queue.offer(source);
    grid[source.x][source.y] = true;
    int ans = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            Point cur = queue.poll();
            //到达终点，返回距离
            if (cur.x == destination.x && cur.y == destination.y)  {
                return ans;
            }
            for (int i = 0; i < 8; i++) {
                Point next = new Point (
                    cur.x + dx[i],
                    cur.y + dy[i]
                );
                //判断下一条可否到达
                if (is_in_bound(next,n,m) && grid[next.x][next.y] == false) {
                    queue.offer(next);
                    grid[next.x][next.y] = true;
                }
            }
        }
        ans++;
    }
    return -1;
}
//判断是否越界
private boolean is_in_bound(Point next,int n,int m) {
    return 0 <= next.x && next.x < n && 0 <= next.y && next.y < m;
}           

}

更多题解参考：

九章算法官网