腐烂的橘子

题目链接：腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

方法一：广度优先遍历

class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    int cnt;
    int dis[10][10];
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> q;
        memset(dis,-1,sizeof dis);
        cnt = 0;
        int ans = 0;
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0;j < grid[0].size();j++) {
                if (grid[i][j] == 2) {
                    dis[i][j] = 0;
                    q.push({i,j});
                }else if (grid[i][j] == 1) cnt++;
            }
        }
        while (!q.empty()) {
            pair<int,int> p = q.front();
            q.pop();
            for (int i = 0;i < 4;i++) {
                int tx = p.first+dx[i];
                int ty = p.second+dy[i];
                if (tx < 0 || tx >= grid.size() || ty < 0 || ty >= grid[0].size() || dis[tx][ty] != -1 || !grid[tx][ty]) continue;
                //cnt--;
                dis[tx][ty] = dis[p.first][p.second] + 1;
                q.push({tx,ty});
                if (grid[tx][ty] == 1) {
                    cnt --;
                    ans = dis[tx][ty];
                    if (cnt == 0) {
                        
                        break ;
                    }
                }
            }
        }
        return cnt ? -1 : ans;
    }
};