【LeetCode】1091. 二进制矩阵中的最短路径

一、题目

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）C_1 位于(0, 0)（即，值为 grid[0][0]）C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）

示例 1：

输入：[[0,1],[1,0]]

输出：2

示例 2：

输入：[[0,0,0],[1,1,0],[1,1,0]]

输出：4

提示：

1.1 <= grid.length == grid[0].length <= 100 2.grid[i][j] 为 0 或 1

二、解决

1、暴力

思路： 略。 代码： 略。 时间复杂度： $O(?)$ 空间复杂度： $O(?)$

2、DP

思路：

1、状态定义 dp[x][y]：从（0，0）到（x,y）位置的 2、状态方程 dp[i][j] = min{dp[new_i][new_j]+1, dp[i][j]}, dp[new_i][new_j]有效 -- 注意上下限 & 八连通

代码： 未通过，暂略。 时间复杂度： $O(n^2)$ 空间复杂度： $O(n^2)$

3、BFS

思路：

先附一下BFS模板：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List<List<Integer>> BFS(TreeNode root) { List<List<Integer>> allResults = new ArrayList<>(); if (root == null) return allResults; Queue<TreeNode> nodes = new LinkedList<>(); nodes.add(root); while (!nodes.isEmpty()) { int levelSize = nodes.size(); List<Integer> results = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currNode = nodes.poll(); results.add(currNode.val); if (currNode.left != null) nodes.add(currNode.left); if (currNode.right != null) nodes.add(currNode.right); } allResults.add(results); } return allResults; }

这里原理类似，从左上方向右下方逐层扩展，直到遇到最右下角的位置，返回对应长度。这里需要改动上述模板的地方有：数据结构变了，随之将TreeNode改成directions方向向量。所有的代码块具体内容随之做出合适的改变。

代码：

public class shortestPathBinaryMatrix { private static int[][] directions = {{0,1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {-1, -1}, {-1, 0}, {-1, 1}}; private int row, col; public int shortestPathBinaryMatrix(int[][] grid) { row = grid.length; col = grid[0].length; if (grid[0][0] == 1 || grid[row - 1][col - 1] == 1) return -1; Queue<int[]> pos = new LinkedList<>(); grid[0][0] = 1; // 直接用grid[i][j]记录从起点到这个点的最短路径长。按照题意 起点也有长度1 pos.add(new int[]{0,0}); while(!pos.isEmpty() && grid[row - 1][col - 1] == 0) { // 求最短路径 使用BFS int[] xy = pos.remove(); int preLength = grid[xy[0]][xy[1]]; // 当前点的路径长度 for(int i = 0; i < 8; i++) { int newX = xy[0] + directions[i][0]; int newY = xy[1] + directions[i][1]; if(inGrid(newX, newY) && grid[newX][newY] == 0) { pos.add(new int[]{newX, newY}); grid[newX][newY] = preLength + 1; // 下一个点的路径长度要+1 } } } return grid[row - 1][col - 1] == 0 ? -1 : grid[row - 1][col - 1]; // 如果最后终点的值还是0，说明没有到达 } private boolean inGrid(int x, int y){ return x >= 0 && x < row && y >= 0 && y < col; } }

时间复杂度： $O(n^2)$，n = grid.length 空间复杂度： $O(n^2)$

4、双向BFS

思路：

先简单解释下双向BFS：

已知目标顶点（即终点），可从分别起点和终点执行BFS，直到遍历有交集，这种方式搜索的单词数量会更小点。而且每次可以从单词数量少的集合开始扩散，以提升速度。

这里 start(visited) 和 end(visited) 交替使用，等价于单向 BFS 里使用队列，每次扩散都要加到总的 visited 里。

再附一下双向BFS模板。 public int doubleBFS(ElementType start, ElementType end) { if (start == end) return 1; # 分别从起点和终点开始的两个BFS队列 Queue<TreeNode> startQueue = new LinkedList<>(); Queue<TreeNode> endQueue = new LinkedList<>(); startQueue.add(start); endQueue.add(end); # 从起点开始和从终点开始分别访问过的节点集合.有时候startQueue与startVisited只需要一个，或者二合一 Set<ElementType> startVisited = new HashSet<>(); Set<ElementType> endVisited = new HashSet<>(); startVisited.add(start) endVisited.add(end) Queue<ElementType> tempQueue = new LinkedList<>(); Set<ElementType> tempVisited = new HashSet<>(); step = 0; while (!startQueue.isEmpty()) { startSize, = startQueue.size(); //　按层遍历 step++; for (int i = 0; i < startSize; i++) { ElemnetType cur = startQueue.poll(); for (ElemnetType neighbor : cur) { // 重复节点 if (neighbor in startVisited) continue; // 相交 else if (neighbor in endVisited) return step; else { startVisited.add(neighbor); startQueue.add(neighbor); } } // 交换 if (startQueue.size() > endQueue.size()) { tempQueue = startQueue; tempVisited = startVisited; endVisited = startVisited ; endQueue = startQueue; startVisited = tempVisited; endQueue = tempVisited; } } return -1; }

与下面代码对比一下，可以分析出下面的代码符合上面模板的大致步骤。

代码：

class Solution { public int shortestPathBinaryMatrix(int[][] grid) { if (grid == null || grid.length == 0) return -1; if (grid.length == 1) { return grid[0][0] == 0? 1: 0; } int M = grid.length; int N = grid[0].length; if (grid[0][0] == 1 || grid[M - 1][N - 1] == 1) return -1; boolean[][] headMemo = new boolean[M][N]; boolean[][] tailMemo = new boolean[M][N]; Queue<Integer> headQueue = new ArrayDeque<>(); Queue<Integer> tailQueue = new ArrayDeque<>(); int[] dirs = {0,1,-1,-1,0,-1,1,1,0}; int dist = 2; headMemo[0][0] = true; tailMemo[M - 1][N - 1] = true; headQueue.offer(0); tailQueue.offer((M - 1) * N + (N - 1)); while (!headQueue.isEmpty()) { int size = headQueue.size(); while (size-- > 0) { int t = headQueue.poll(); int row = t / N; int col = t % N; for (int k = 1; k < dirs.length; k++) { int r = row + dirs[k - 1]; int c = col + dirs[k]; if (r >= 0 && c >= 0 && r < M && c < N && grid[r][c] != 1 && !headMemo[r][c]) { if (tailMemo[r][c]) return dist; headMemo[r][c] = true; headQueue.offer(r * N + c); } } } dist++; if (headQueue.size() > tailQueue.size()) { boolean[][] tempMemo = headMemo; headMemo = tailMemo; tailMemo = tempMemo; Queue<Integer> tempQ = headQueue; headQueue = tailQueue; tailQueue = tempQ; } } return -1; } }

时间复杂度： $O(n^2)$，n = grid.length 空间复杂度： $O(n^2)$

5、启发式

思路：

先附一下二叉树的启发式搜索算法模板。

public List<List<Integer>> aStarSearch(TreeNode root) { List<List<Integer>> allResults = new ArrayList<>(); if (root == null) return allResults; PriorityQueue<TreeNode> nodes = new PriorityQueue<>(); // 优先级（一种可能） —> 估价函数 nodes.add(root); while (!nodes.isEmpty()) { int levelSize = nodes.size(); List<Integer> results = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currNode = nodes.poll(); // can we add more intelligence here ? results.add(currNode.val); if (currNode.left != null) nodes.add(currNode.left); if (currNode.right != null) nodes.add(currNode.right); } allResults.add(results); } return allResults; }

这里数据结构有差异，用的是数组，所以还是需要根据情况进行变化。

代码：

class Solution { class Node implements Comparable<Node> { int x, y, f; Node(int x, int y, int f) { this.x = x; this.y = y; this.f = f; } @Override public int compareTo(Node n) { return this.f - n.f; } } int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}}; int m, n; public int shortestPathBinaryMatrix(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return -1; m = grid.length; n = grid[0].length; if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1; if (n == 1) return 1; // corner case int[][] dist = new int[m][n]; int[][] visited = new int[m][n]; PriorityQueue<Node> queue = new PriorityQueue<>(); dist[0][0] = 1; queue.add(new Node(0, 0, h(0, 0))); while (!queue.isEmpty()) { Node node = queue.poll(); int i = node.x, j = node.y; if (visited[i][j] == 2) continue; // avoid duplicate nodes visited[i][j] = 2; for (int[] dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; if (x < 0 || x >= m || y < 0 || y >= n) continue; if (grid[x][y] == 1 || visited[x][y] == 2) continue; // blocked or visited if (x == m - 1 && y == n - 1) return dist[i][j] + 1; // find end if (visited[x][y] == 0 || dist[x][y] > dist[i][j] + 1) { // update cost dist[x][y] = dist[i][j] + 1; visited[x][y] = 1; queue.add(new Node(x, y, dist[x][y] + h(x, y))); } } } return -1; // cannot reach end } private int h(int x, int y) { return Math.max(m - 1 - x, n - 1 - y); // Chebyshev distance } }

时间复杂度： $O(n^2)$ 空间复杂度： $O(n^2)$

三、参考

1、1091.java BFS直接打败98% 详解 2、JAVA BFS 3、Java BFS Solution 4、简单易懂的c++ dp做法 5、Swift DP soultion 6、Java Bidirectional BFS. Faster than 99%. 7、A* search in Python 8、Java A* Search， 执行用时：15 ms 9、[Java/Python 3] concise BFS and DFS codes w/o changing input.