题目

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路
每一轮，腐烂将会从每一个烂橘子蔓延到与其相邻的新鲜橘子上。一开始，腐烂的橘子的深度为 0，每一轮腐烂会从腐烂橘子传染到之相邻新鲜橘子上，并且设置这些新的腐烂橘子的深度为自己深度 +1，我们想知道完成这个过程之后的最大深度值是多少。
算法
我们可以用一个广度优先搜索来建模这一过程。因为我们总是选择去使用深度值最小的（且之前未使用过的）腐烂橘子去腐化新鲜橘子，如此保证每一个橘子腐烂时的深度标号也是最小的。
我们还应该检查最终状态下，是否还有新鲜橘子。

作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/fu-lan-de-ju-zi-by-leetcode/

代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {        
        if(grid.empty()||grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<pair<int, int>> directs {
  {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        queue<pair<int, int>> q;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) ++count;
                if (grid[i][j] == 2) q.push(make_pair(i, j));
            }
        }
        if (count == q.size()) return 0;
        int res = 0;
        while (!q.empty()) {
            for (int size = q.size(); size > 0; size--) {
                auto pos = q.front();q.pop(); 
                count --;
                int x = pos.first, y = pos.second;
                for (auto d: directs) {
                    int nx = x + d.first, ny = y + d.second;
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != 1) continue;
                    grid[nx][ny] = 2;
                    q.push(make_pair(nx, ny));
                    
                }
            }
            res ++;
        }
        return count == 0 ? res - 1 : -1;
    }
};

总结

  1. 用方向数组来求四个方向的next的坐标。
  2. 我们可以用一个广度优先搜索来建模这一过程。因为我们总是选择去使用深度值最小的（且之前未使用过的）腐烂橘子去腐化新鲜橘子，如此保证每一个橘子腐烂时的深度标号也是最小的。
  3. 层次遍历，一层一层的解决求出最后解的。