编写c++程序:在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一: 值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
时间: 2024-04-17 21:26:37 浏览: 207
一个关于c++程序的小例题
你好!下面是一个解决上述问题的C++程序:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> rotten; // 存放腐烂的橘子的坐标
int freshCount = 0; // 记录新鲜橘子的数量
// 遍历网格,将腐烂的橘子和新鲜橘子分别存入队列和计数器
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
freshCount++;
} else if (grid[i][j] == 2) {
rotten.push({i, j});
}
}
}
int minutes = 0;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
while (!rotten.empty() && freshCount > 0) {
int size = rotten.size();
for (int i = 0; i < size; i++) {
pair<int, int> curr = rotten.front();
rotten.pop();
for (auto dir : directions) {
int x = curr.first + dir.first;
int y = curr.second + dir.second;
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2; // 将新鲜橘子腐烂
rotten.push({x, y});
freshCount--;
}
}
}
minutes++;
}
return freshCount == 0 ? minutes : -1;
}
int main() {
// 示例测试
vector<vector<int>> grid = {{2,1,1},{1,1,0},{0,1,1}};
cout << orangesRotting(grid) << endl; // 输出3
return 0;
}
```
这个程序使用广度优先搜索算法来模拟橘子的腐烂过程。首先,遍历网格,将腐烂的橘子和新鲜橘子分别存入队列和计数器。然后,不断循环直到队列为空或者没有新鲜橘子为止。每次循环中,取出队列中的腐烂橘子,检查其上下左右四个方向上的格子,如果是新鲜橘子,则将其标记为腐烂并加入队列中,同时更新新鲜橘子的数量。最后,返回新鲜橘子数量是否为0,如果是则返回经过的分钟数,否则返回-1。
以上是一个示例程序,你可以根据需要进行修改和调试。希望对你有帮助!如果还有其他问题,请随时提问。
阅读全文