题目

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1instead.

Example 1:

image

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
**Explanation: ** The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
**Explanation: ** Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

解答

想了半天，没想出简便的方法，于是看了下答案，了解了下思路，然后自己手写了一遍。改进了一下原答案中使用map存结果的方法。

思路是这样的：
先一遍循环，把数组中所有的2的坐标存进一个队列中。这是初始状态。比如有5个2，那么就存住了5个2的坐标，接着，从队列中取出每一个2的坐标，对它的上下左右进行处理，判断边界啊，判断是不是1啊，是1就变成2啊，然后如果变成了2，就再把这个新的2的坐标存到队列中，但是本轮不处理它，本轮只处理一开始的5个2。

这样5个2处理完了，可能又新产生了4个2，然后下一轮再处理这4个2，直到队列为空，也就是说，没有新产生2了。

// 这两个数组是用来迭代相邻位置的，上下左右
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};

public int orangesRotting(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return -1;
    }

    final int R = grid.length;
    final int C = grid[0].length;

    Queue<Integer> queue = new ArrayDeque<>();

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == 2) {
                int code = i * C + j; // 将一个二维坐标编码成一个数字存进队列
                queue.add(code);
            }
        }
    }

    int count = 0;

    while (!queue.isEmpty()) {

        int length = queue.size(); // 只处理当前长度，因为这个过程会生产一些放入队列，但是是下一轮再处理

        boolean isRot = false; // 标记是否有腐烂操作

        for (int i = 0; i < length; i++) {
            int code = queue.poll();
            int r = code / C; int c = code % C;

            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];

                if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1) {
                    // 标记腐烂操作，然后再将新的腐烂的橘子放到队列中
                    isRot = true;
                    grid[nr][nc] = 2;
                    queue.add(nr * C + nc);
                }
            }
        }

        // 有腐烂操作，时间+1
        if (isRot) {
            count++;
        }
    }

    // 迭代一遍，如果还有1，说明是不相邻的，没法腐烂到它，返回-1
    for (int[] row : grid) {
        for (int v : row) {
            if (v == 1) {
                return -1;
            }
        }
    }

    return count;
}