多源bfs，LeetCode 994. 腐烂的橘子

本文主要是介绍多源bfs，LeetCode 994. 腐烂的橘子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

2、接口描述

python3

​

class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:

cpp

​

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {}
};

3、原题链接

994. 腐烂的橘子

---

二、解题报告

1、思路分析

初始遍历网格将所有腐烂橘子入队，同记录当前所有的新鲜橘子个数

如果队列不空并且有新鲜橘子，我们就将当前队列的坐标全部出队扩展一层，只能扩展那些新鲜橘子的格子，并将其改为不新鲜

最终返回时如果仍有新鲜橘子就返回-1，否则返回bfs扩展的层数即时间

2、复杂度

时间复杂度： O(NM) 空间复杂度：O(NM)

3、代码详解

python3

​

class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])q = []tot = 0for i, row in enumerate(grid):for j, x in enumerate(row):if x == 1:tot += 1elif x == 2:q.append((i, j))ret = 0while q and tot:ret += 1nq = []for x, y in q:for nx, ny in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):if nx < 0 or ny < 0 or nx >= m or ny >= n or grid[nx][ny] != 1:continuegrid[nx][ny] = 2tot -= 1nq.append((nx, ny))q = nqreturn ret if tot == 0 else -1

cpp

​

class Solution {
public:
typedef pair<int, int> PII;
static constexpr int dst[5] { 1, 0, -1, 0, 1 };int orangesRotting(vector<vector<int>>& grid) {queue<PII> q;int m = grid.size(), n = grid[0].size();int ret = 0, tot = 0;for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++)if (grid[i][j] == 2) q.emplace(i, j);else if(grid[i][j] == 1) tot ++;while (q.size() && tot) {ret ++;for(int i = 0, ed = q.size(); i < ed; i ++) {auto [x, y] = q.front();q.pop();for (int j = 0; j < 4; j ++) {int nx = x + dst[j], ny = y + dst[j + 1];if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;if (grid[nx][ny] != 1) continue;tot -= grid[nx][ny];grid[nx][ny] = 2;q.emplace(nx, ny);}}}return tot ? -1 : ret;}
};

这篇关于多源bfs，LeetCode 994. 腐烂的橘子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---