20 届秋招。

给定骑士在棋盘上的 初始 位置(一个 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)

样例

例 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],  [0,0,0]] source = [2, 0] destination = [2, 2]  输出:-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;     } } 

猪场的待遇咋样啊。。