1091. 二进制矩阵中的最短路径(标准BFS)

本文主要是介绍1091. 二进制矩阵中的最短路径(标准BFS)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格都的值都是 0 。
• 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：2

示例 2：

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] 为 0 或 1

 1 class Solution {
 2 public:
 3     static constexpr int g_directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}; // 8个方向
 4     bool isInArea(int row, int col, int x, int y) {
 5         return (x >= 0 && x < row && y >= 0 && y < col);
 6     }
 7     int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
 8         // 题目中不会出现,因为n >= 1
 9         if (grid.empty()) {
10             return -1;
11         }
12         int n = grid.size();
13         // 当起点或者终点不为0时,不能走
14         if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
15             return -1;
16         }
17         vector<vector<bool>> visited(n, vector<bool>(n, false)); // 访问标记
18         queue<std::pair<int, int>> q;
19         q.push({0, 0}); // 起点坐标入队
20         visited[0][0] = true; // 标记起点已访问
21         int step = 1; // 畅通路径的长度
22         while (!q.empty()) {
23             int size = q.size();
24             for (int i = 0; i < size; i++) {
25                 auto [curX, curY] = q.front();
26                 q.pop();
27                 // 到达终点坐标时返回最短畅通路径长度
28                 if (curX == n - 1 && curY == n - 1) {
29                     return step;
30                 }
31                 for (auto &direction : g_directions) {
32                     int nextX = curX + direction[0];
33                     int nextY = curY + direction[1];
34                     // 越界或者已访问的跳过
35                     if (!isInArea(n, n, nextX, nextY) || visited[nextX][nextY]) {
36                         continue;
37                     }
38                     // 不能通过的跳过
39                     if (grid[nextX][nextY] != 0) {
40                         continue;
41                     }
42                     q.push({nextX, nextY});
43                     visited[nextX][nextY] = true;
44                 }
45             }
46             step++;
47         }
48         return -1;
49     }
50 };

这篇关于1091. 二进制矩阵中的最短路径(标准BFS)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！