LeetCode 994. 腐烂的橘子（图的BFS）

示例 1：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int i, j, k, len, x, y, goodfruits = 0;
        int m = grid.size(), n = grid[0].size(), minutes = -1;
        queue<pair<int,int>> q;
        for(i = 0; i < m; ++i)
        	for(j = 0; j <n; ++j)
        		if(grid[i][j] == 2)
        		{
        			q.push({i,j});//烂橘子入队
        			grid[i][j] = -1;//访问过了
        		}
        		else if(grid[i][j] == 1)
        			goodfruits++;//好橘子个数
		if(goodfruits == 0)
			return 0;//没有好橘子，直接返回
		vector<pair<int,int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};
		while(!q.empty())
		{
			len = q.size();
			while(len--)
			{
				for(k = 0; k < 4; ++k)
				{
					x = q.front().first+dir[k].first;
					y = q.front().second+dir[k].second;
					if(x>=0 && x<m && y>=0 && y<n && grid[x][y]!= -1 && grid[x][y]==1)
					{	//没访问过 && 是好橘子
						q.push({x,y});
						grid[x][y] = -1;//访问了
						goodfruits--;//烂了
					}
				}
				q.pop();
			}
            ++minutes;
		}
		if(goodfruits)
			return -1;//还有好橘子，所以不可能全烂掉
		return minutes;
    }
};