在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
示例 1:
输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
输出:4
> 代码
class Solution {
int dirt[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
public:
int orangesRotting(vector<vector<int>>& grid) {
int min = 0, fresh = 0;///fresh记录每一个新鲜的水果,min为记录层数
//队列,保存一对坐标
queue<pair<int, int>>que;
//遍历地图
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1)fresh++; //记录新鲜水果的数量
else if (grid[i][j] == 2) que.push({ i,j });//记录腐烂水果坐标
}
}
//层序遍历,while(直到没有元素)
//保存对首元素,
//遍历层的元素
//遍历层的四周元素
//如果符合就标记走过,添加到新的队列,并且水果新鲜-1
while (!que.empty()) {
int n = que.size();
bool rotten = false;
//遍历队列一层的元素
for (int i = 0; i < n; i++) {
auto x = que.front(); //保存腐烂元素的坐标
que.pop(); //出队列
for (auto cur : dirt) {
int i = x.first + cur[0]; //更新x的坐标
int j = x.second + cur[1]; //更新y的坐标
//如果遍历的坐标是新鲜的和符合要求的
if (i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1) {
grid[i][j] = 2; //更新坐标
que.push({ i,j }); //加入队列
fresh--; //新鲜数量减一
rotten = true; //标记遍历完一层
}
}
}
if (rotten) min++; //遍历完一层,记录+1
}
return fresh ? -1 : min; //如果fresh为0,全完腐烂,返回min
//如果fresh不为0,表示还有新鲜的,返回-1
}
};
标签:994,遍历,int,腐烂,grid,fresh,que,橘子
From: https://www.cnblogs.com/lihaoxiang/p/17722484.html