题解 | #腐烂的苹果#C++

这个应该是个多源bfs问题，但我目前没有学，只学了普通的bfs，偶然想到二叉树的层序遍历使用了队列的效果达到挨个出现，所以想到这个问题的腐蚀扩散也可以使用队列来模拟进行

class Solution
{
  public:
  int Max = 0;//记录需要多少分钟
  int num1 = 0;//记录好苹果的个数
  queue<pair<int, int>>q;
  queue<pair<int, int>>p;
  bool dfs(vector<vector<int> >& grid, int row, int col)//遍历一遍是否有出现不能被腐烂的苹果
  {
	  if (row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size() || grid[row][col] == 0)
	  {
		  return true;
	  }

	  if (grid[row][col] == 2)
	  {
		  return false;
	  }
	  grid[row][col] = 0;
	  bool found = dfs(grid, row + 1, col)
		  && dfs(grid, row - 1, col)
		  && dfs(grid, row, col + 1)
		  && dfs(grid, row, col - 1);
	  grid[row][col] = 1;
	  return found;
  }
  void dfs2(vector<vector<int> >& grid, int row, int col, int& k)//这个函数负责进行腐烂扩散操作
  {
	  //分别对上下左右进行判断，如果为好苹果且没越界，就进行腐烂操作
	  if (row + 1 >= 0 && col >= 0 && row + 1 < grid.size() && col < grid[0].size() && grid[row + 1][col] == 1)
	  {
		  k += 1;
		  p.push({ row + 1,col });
		  grid[row + 1][col] = 2;

	  }
	  if (row - 1 >= 0 && col >= 0 && row - 1 < grid.size() && col < grid[0].size() && grid[row - 1][col] == 1)
	  {
		  k += 1;

		  p.push({ row - 1,col });
		  grid[row - 1][col] = 2;
	  }
	  if (row >= 0 && col + 1 >= 0 && row < grid.size() && col + 1 < grid[0].size() && grid[row][col + 1] == 1)
	  {
		  k += 1;

		  p.push({ row ,col + 1 });
		  grid[row][col + 1] = 2;
	  }
	  if (row >= 0 && col - 1 >= 0 && row < grid.size() && col - 1 < grid[0].size() && grid[row][col - 1] == 1)
	  {
		  k += 1;

		  p.push({ row ,col - 1 });
		  grid[row][col - 1] = 2;

	  }
  }

  int rotApple(vector<vector<int> >& grid)
  {
	  int row = grid.size(), col = grid[0].size();
	  for (int i = 0; i < row; ++i)
	  {
		  for (int j = 0; j < col; ++j)
		  {
			  if (grid[i][j] == 1)
			  {
				  num1 += 1;
				  if (dfs(grid, i, j))//如果为1就检测是否会出现不能被腐蚀的苹果
				  {
					  return -1;
				  }

			  }
			  if (grid[i][j] == 2)
			  {
				  q.push({ i,j });//搜索到2就把插入到队列中
			  }
		  }
	  }


	  int time = 1;//记录多少层
	  int k = 0;
	  while (!q.empty())//一开始的q里存的全是对应的烂苹果坐标
	  {
		  while (!q.empty())
		  {
			  auto ret = q.front();
			  q.pop();
			  dfs2(grid, ret.first, ret.second, k);
			  if (k == num1)
			  {
				  return time;
			  }
		  }
		  time += 1;
		  q = p;
	  }

	  return time;
  }

};