题目链接：腐烂的苹果_牛客题霸_牛客网 (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 相关算法学习完，并将其算法原理熟烂于心。
