腐烂的橘子

题干

这题本质上考察的就是广度优先搜索。我们假设只有一个腐烂的橘子，这种情况比较好说明。那么我们从这个腐烂的橘子的上下左右四个方向开始BFS,每次遍历到一个新鲜的橘子，我们就把它腐烂。注意到BFS一般会借助队列来实现，那我刚开始肯定是把腐烂的橘子的位置加入队列，然后从队列中弹出并进行腐烂操作。等到队列为空时，我再来看看是否还存在新鲜的橘子，并据此输出答案。

但是这只是特殊情况，我们需要考虑一般情况，因为一般来说不会只有一个腐烂的橘子。那怎么办呢？我们建立一个超级源点就好了。首先，把格子中所有腐烂橘子的坐标全部加入队列中，这些位置本质上就是一个位置。至于次数，我们使用二维数组来完成处理，每遍历到一个新鲜橘子，我们就把最近腐烂橘子（也就是广度优先搜索的那个中心点）的值加上1作为其在二维数组中的位置的值，也就是次数。等到遍历完成后，这个次数一定是最少的，因为届时就没有新鲜橘子可以抵达了，这一点可以仔细想想。

代码：

package com.hw.test;

import java.util.LinkedList;
import java.util.Queue;

public class RottingOranges {
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private Queue<int[]> q = new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        int ans = 0;
        boolean flag = false;
        int row = grid.length, col = grid[0].length;
        int[][] mat = new int[row][col];
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int nx = cell[0], ny = cell[1];
            for (int i = 0; i < 4; ++i) {
                int mx = nx + dx[i];
                int my = ny + dy[i];
                if (mx >= 0 && mx < row && my >= 0 && my < col && grid[mx][my] == 1) {
                    mat[mx][my] = mat[nx][ny] + 1;
                    ans = mat[mx][my];
                    grid[mx][my] = 2;
                    q.offer(new int[]{mx, my});
                }
            }
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1) {
                    flag = true;
                    break;
                }
            }
        }
        return flag ? -1 : ans;
    }
    public static void main(String[] args) {
        int[][] grid = {
                {2, 1, 1},
                {1, 1, 0},
                {0, 1, 1}
        };
        int ans = new RottingOranges().orangesRotting(grid);
        System.out.println(ans);
    }
}