题目链接：腐烂的苹果_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
多源 BFS 问题，加一点最短路的思想，固定套路。
二、代码
//看了题解之后AC的代码
class Solution {
private:int n, m;bool vis[1010][1010];int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param grid int整型vector<vector<>> * @return int整型*/int rotApple(vector<vector<int> >& grid) {n=grid.size(), m=grid[0].size();queue<pair<int, int>> q;for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(grid[i][j]==2)q.push({i, j});int t=0;while(q.size()){t++;int size=q.size();while(size--){auto [a, b]=q.front();q.pop();for(int k=0; k<4; k++){int x=a+dx[k], y=b+dy[k];if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && grid[x][y]==1){vis[x][y]=true;q.push({x, y});}}}}for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(!vis[i][j] && grid[i][j]==1)return -1;return t-1;}
};//值得学习的代码
class Solution
{int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool vis[1010][1010] = { 0 };public:int rotApple(vector<vector<int> >& grid) {m = grid.size(), n = grid[0].size();queue<pair<int, int>> q;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 2)q.push({i, j});int ret = 0;while(q.size()){int sz = q.size();ret++;while(sz--){auto [a, b] = q.front();q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;q.push({x, y});}}}}for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(grid[i][j] == 1 && !vis[i][j]) return -1; return ret - 1;}
};三、反思与改进
这道题目我是用 dfs 做的，暴力过了 70% 的样例，但我很清楚正确答案肯定是要用到 bfs，是层序遍历整个网格，但在做题的时候把 bfs 最基本的内容给忘记了，连其对应辅助的栈结构都没想起来。还有一个主要原因是：多源 bfs 这一块我还没有进行系统性的学习，目前只接触了最基础的 bfs，不过我不认为这是做不出这道题目的理由，究其根本是连本质都忘记了，而不是 bfs 的扩展没学习到，所以要抓紧时间把 bfs 相关算法学习完，并将其算法原理熟烂于心。
