首页 > 分享 > 腐烂橘子扩散算法

腐烂橘子扩散算法

花匠小妙招
2024-12-29 17:12

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

参考：LeetCode题解
方法1：枚举加广度优先搜索
最直观能想到的方法就是枚举加BFS的方法，这里使用一个辅助二维数组用来记录橘子是在第几分钟腐烂的。先遍历一遍地图，存下来开始时所有腐烂橘子的坐标。然后以每个腐烂的橘子的位置为起点，开始进行bfs，如果碰到已经腐烂的橘子，但是腐烂的时间却大于当前时间+1，则需要更新该位置上橘子的腐烂时间。对所有起点进行bfs了之后，再次遍历地图，检查是否还有完好的橘子，以及所需要的时间是多少。

这种方法的缺点是时间复杂度较高，需要在bfs时间复杂度（O(V+E)）的基础上再乘以开始时腐烂的橘子的个数。在网络规格变大时将会十分耗时。

class Solution { public: int orangesRotting(vector<vector<int>>& grid) { vector<vector<int> > decaiedTime; vector<pair<int, int> > decaiedOrange; int maxTime = INT_MIN; for (int i = 0; i < grid.size(); i++){ decaiedTime.push_back(vector<int>()); for (int j = 0; j < grid[0].size(); j++){ if (grid[i][j] == 2){ decaiedTime[i].push_back(0); decaiedOrange.push_back(make_pair(i, j)); } else{ decaiedTime[i].push_back(0); } } } for (int i = 0; i < decaiedOrange.size(); i++){ this->bfs(decaiedOrange[i], grid, decaiedTime); } for (int i = 0; i < grid.size(); i++){ for (int j = 0; j < grid[0].size(); j++){ if (grid[i][j] == 1){ return -1; } else{ maxTime = max(maxTime, decaiedTime[i][j]); } } } return maxTime; } void bfs(pair<int, int> start, vector<vector<int> >& grid, vector<vector<int> >& decaiedTime) { queue<pair<int, int> > bfsQueue; bfsQueue.push(start); int addX[4] = {0, 0, 1, -1}; int addY[4] = {1, -1, 0, 0}; int width = grid.size(); int height = grid[0].size(); while (!bfsQueue.empty()){ int currentX = bfsQueue.front().first; int currentY = bfsQueue.front().second; int currentTime = decaiedTime[currentX][currentY]; bfsQueue.pop(); for (int i = 0; i < 4; i++){ int newX = currentX + addX[i]; int newY = currentY + addY[i]; if (newX < 0 || newX >= width || newY < 0 || newY >= height){ continue; } else if (grid[newX][newY] == 1 || (grid[newX][newY] == 2 && decaiedTime[newX][newY] > currentTime + 1)){ grid[newX][newY] = 2; bfsQueue.push(make_pair(newX, newY)); decaiedTime[newX][newY] = currentTime + 1; } } } } };

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667

方法2：多源广度优先搜索
开始时所有腐烂的橘子本质上是同一层的结点。所以直接进行bfs即可，只需在bfs中跟踪结点的层数，然后更新为最小的层数即可。所以我们在开始时将所有腐烂的橘子都放进bfs队列中，这样只需要进行一次bfs即可。
代码参考LeetCode题解

class Solution{ int cnt; // 统计腐烂的橘子的个数； int dis[10][10]; //用来统计层数 int dir_x[4] = {0, 1, 0, -1}; int dir_y[4] = {1, 0, -1, 0}; public: int orangesRotting(vector<vector<int> > &grid) { queue<pair<int, int> > Q; memset(dis, -1, sizeof(dis)); cnt = 0; int n = (int)grid.size(), m = (int)grid[0].size(), ans = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (grid[i][j] == 2){ Q.push(make_pair(i, j)); dis[i][j] = 0; } else if (grid[i][j] == 1){ cnt += 1; // 腐烂的橘子个数+1； } } } while (!Q.empty()){ pair<int, int> x = Q.front(); //广搜得到队列保证了先后顺序。 Q.pop(); for (int i = 0; i < 4; i++){ int tx = x.first + dir_x[i]; int ty = x.second + dir_y[i]; if (tx < 0 || tx >= n || ty < 0 || ty >= m || ~dis[tx][ty] || !grid[tx][ty]){ continue; } dis[tx][ty] = dis[x.first][x.second] + 1; Q.push(make_pair(tx, ty)); if (grid[tx][ty] == 1){ cnt -= 1; ans = dis[tx][ty]; if (!cnt) break; } } } return cnt ? -1 : ans; } };

1234567891011121314151617181920212223242526272829303132333435363738394041424344