时间复杂度：O(nm)。即进行一次广度优先搜索的时间，其中 n,m 分别为 grid 的行数与列数。
空间复杂度：O(nm)。需要额外的 dis 数组记录每个新鲜橘子被腐烂的最短时间，大小为 O(nm)，且广度优先搜索中队列里存放的状态最多不会超过 nm 个，最多需要 O(nm) 的空间，所以最后的空间复杂度为 O(nm)。
class Solution {
    //在 BFS 或 DFS 遍历中，这两个数组用于计算从当前单元格 (r, c) 到相邻单元格的坐标
    //dr（row direction）表示在行方向上的偏移量。向上、向左、向下和向右的行偏移量
    int[] dr = new int[]{-1, 0, 1, 0};
    //dc（column direction）表示在列方向上的偏移量。向上、向左、向下和向右的列偏移量
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        //每个橘子对应的腐烂时间
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {//将所有腐烂的橘子加入到队列中
                    int code = r * C + c;//编码
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;//ans 记录了这些腐烂时间的最大值，也就是所有橘子完全腐烂所需的最长时间
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;//解码
            for (int k = 0; k < 4; ++k) {//用于计算从当前单元格 (r, c) 到相邻单元格的坐标
                int nr = r + dr[k];//上左下右移动找到新鲜橘子
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);//每一次腐烂别的橘子时都+1，depth 中存储了所有被腐烂的橘子的最短腐烂时间
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row: grid) {
            for (int v: row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}