题目

题目描述

存在一个 m × n的二维数组，其成员取值范围为 0 或 1，其中值为 1 的成员具备扩散性，每经过 1S，将上下左右值为 0 的成员同化为 1，二维数组的成员初始值都为 0，将第 [i, j] 和 [k, l] 两个个位置上元素修改成 1 后，求矩阵的所有元素变为 1 需要多长时间。

输入描述

输入数据中的前 2 个数字表示这是一个 m × n 的矩阵，m 和 n 不会超过 1024 大小；

中间 2 个数字表示一个初始扩散点位置为 i, j

最后 2 个数字表示另一个扩散点位置为 k, l

输出描述

输出矩阵的所有元素变为 1 所需要秒数。

示例

输入：

4,4,0,0,3,3

输出：

3

说明：

输入数据中的前2个数字表示这是一个4×4的矩阵；

中间两个数字表示一个初始扩散点位置为0,0；

最后2个数字表示另一个扩散点位置为3,3；

给出的样例是一个简单模型，初始点在对角线上，达到中间的位置分别是3次迭代，即3秒。所以输出位3。

解题思路

典型的多源 BFS、时间扩散问题。

2 个源已经定义好了，初始化一个 grid，默认全是 0，把 2 个网格置为1。

把 2 个源放到 queue 中，进行 BFS 扩散，统计层数，层数即扩散时间。

代码

public class MatrixDiffusion {

    public int solution(int m, int n, int[] point1, int[] point2) {
        int[][] grid = new int[m][n];
        grid[point1[0]][point1[1]] = 1;
        grid[point2[0]][point2[1]] = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(point1);
        queue.offer(point2);
        int step = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir : dirs) {
                    int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        grid[nx][ny] = 1;
                        queue.offer(new int[] {nx, ny});
                    }
                }
            }
            step++;
        }
        return step - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] numbers = line.split(",");
        int m = Integer.parseInt(numbers[0]);
        int n = Integer.parseInt(numbers[1]);
        int[] point1 = new int[] {Integer.parseInt(numbers[2]), Integer.parseInt(numbers[3])};
        int[] point2 = new int[] {Integer.parseInt(numbers[4]), Integer.parseInt(numbers[5])};
        // 算法
        MatrixDiffusion matrixDiffusion = new MatrixDiffusion();
        System.out.println(matrixDiffusion.solution(m, n, point1, point2));
    }
}