二进制矩阵中的最短路径【LC1091】
你驾驶出租车行驶在一条有
n个地点的路上。这n个地点从近到远编号为1到n，你想要从1开到n，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。乘客信息用一个下标从 0 开始的二维数组
rides表示，其中rides[i] = [starti, endi, tipi]表示第i位乘客需要从地点starti前往endi，愿意支付tipi元的小费。每一位 你选择接单的乘客
i，你可以 盈利endi - starti + tipi元。你同时 最多 只能接一个订单。给你
n和rides，请你返回在最优接单方案下，你能盈利 最多 多少元。**注意：**你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。
- 思路常规BFS，使用队列进行BFS，搜索时记录搜索的轮数。搜索到一个可以访问的节点时，将其入队。如果搜索到终点时，直接返回当前轮数；如果队列为空仍为访问到终点，那么返回-1；
- 访问过一个节点后，为了避免重复访问直接将给节点设置为-1
- 实现
class Solution { public int shortestPathBinaryMatrix(int[][] grid) { // BFS int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {0, -1}, {-1, 0}, {-1, -1}, {1, -1}, {-1, 1}};// 8个方向？ Deque<int[]> queue = new LinkedList<>(); int n = grid.length; int count = 0; if (grid[0][0] == 0){ queue.add(new int[]{0, 0}); } while(!queue.isEmpty()){ int size = queue.size(); count++; for (int i = 0; i < size; i++){ int[] p = queue.poll(); int x = p[0], y = p[1]; if (x == n - 1 && y == n - 1) return count; for (int[] dir : dirs){ int x1 = x + dir[0], y1 = y + dir[1]; if (x1 >= 0 && y1 >= 0 && x1 <n && y1 < n && grid[x1][y1] != 1){ queue.add(new int[]{x1, y1}); grid[x1][y1] = 1; } } } } return -1; } }
