用C++解决Leetcode 542
时间: 2024-09-07 08:02:44 浏览: 42
LeetCode 542题是要求实现一个算法,将一个给定的二维数组(0代表墙,1代表空地,2代表细菌)按以下规则进行更新:
- 任何1都会被更新为2;
- 每个1旁边的空地(与1在上下左右相邻),会按顺序变为1;
- 根据更新规则,墙(0)不变。
这个问题可以用广度优先搜索(BFS)解决。我们可以从所有初始为2的细菌开始,将其周围的空地依次更新为1。我们从这些初始的细菌出发,将它们的相邻位置放入队列中,然后不断从队列中取出位置进行更新,直到队列为空。
以下是一个可能的C++解决方案:
```cpp
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> ans(m, vector<int>(n, INT_MAX));
queue<pair<int, int>> q;
// 初始化,将所有的细菌位置加入队列,并记录答案中的距离
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 2) {
q.push({i, j});
ans[i][j] = 0;
}
}
}
// 广度优先搜索
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] > ans[x][y] + 1) {
ans[nx][ny] = ans[x][y] + 1;
q.push({nx, ny});
}
}
}
return ans;
}
};
```
在这段代码中,首先创建了一个方向数组`dirs`来表示上下左右四个方向。接着,初始化一个同样大小的二维数组`ans`来存储每个位置到最近细菌的距离,并将所有的细菌位置和初始距离0加入队列中。然后执行广度优先搜索,对于队列中的每个位置,将其相邻的空地加入队列,并更新`ans`数组中相应位置的值为当前位置到最近细菌的最短距离。
阅读全文