C++解决:给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 1 的距离。 两个相邻元素间的距离为 1 。
时间: 2024-09-07 20:02:48 浏览: 61
要解决这个问题,我们可以使用广度优先搜索(BFS)算法。具体步骤如下:
1. 遍历矩阵,找到所有值为1的元素的位置,并将它们加入队列中。
2. 使用BFS,从队列中的每个位置开始,向上下左右四个方向进行搜索,更新矩阵中对应位置的距离。
3. 对于每个方向,如果遇到的新位置的值为0,更新该位置的距离,并将其加入队列继续进行下一轮的BFS。
4. 重复步骤3,直到队列为空,此时矩阵中每个位置的距离值已经是最小的。
以下是C++代码实现:
```cpp
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size();
int n = mat.size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
queue<pair<int, int>> q;
// 初始化队列,将所有值为1的元素加入队列
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
q.emplace(i, j);
}
}
}
// 方向数组,表示上下左右四个方向
const vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (const auto& dir : dirs) {
int nr = r + dir.first;
int nc = c + dir.second;
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
q.emplace(nr, nc);
}
}
}
}
return dist;
}
```
这段代码首先初始化一个同样大小的矩阵 `dist` 来存储距离信息,然后将所有值为0的位置的距离初始化为0,并将这些位置加入队列。接着,使用BFS逐个处理队列中的位置,对每个位置的相邻四个方向进行检查和更新,直到队列为空。最终返回更新后的 `dist` 矩阵。
阅读全文