腐烂的苹果

腐烂的苹果

• 题目
• 题解(9)
• 讨论(8)
• 排行
• 面经

  new

 时间限制：1秒  空间限制：256M

知识点广度优先搜索(BFS)

描述

给定一个 𝑛×𝑚 n×m  的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围： 1≤𝑛,𝑚≤1000 1≤n,m≤1000  ，网格中的值满足 0≤𝑣𝑎𝑙≤2 0≤val≤2 

思路：

广度递归的做法，每次将当前所有的2所在的下标放入队列中，然后依次取出本次的下标，看四周是否有可以被污染的苹果，如果有就把下标放入队列中。

最后看是否还有未被污染的苹果，有就返回-1.

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param grid int整型vector<vector<>> * @return int整型*/vector<pair<int,int>>kk={{1,0},{-1,0},{0,-1},{0,1}};int rotApple(vector<vector<int> >& grid) {// write code herequeue<pair<int,int>>qn;int row=grid.size();int col=grid[0].size();for(int i=0;i<row;i++)for(int j=0;j<col;j++)if(grid[i][j]==2)qn.push({i,j});int ret=0;while(!qn.empty()){  int size=qn.size();ret++;while(size--){auto it=qn.front();qn.pop();//cout<<it.first<<":"<<it.second<<";";for(int i=0;i<4;i++){int x1=it.first+kk[i].first;int y1=it.second+kk[i].second;if(x1>=0&&x1<row&&y1>=0&&y1<col&&grid[x1][y1]==1){qn.push({x1,y1});grid[x1][y1]=2;}}}}for(auto e:grid){for(auto k:e){if(k==1)return -1;}}return ret-1;}
};