1、前言

2、思路

本题的一个主要思路是多源 bfs，多源在于它有多个源头，可以一起开始 bfs（跟多线程无关）。有多源 bfs 那么就有单源 bfs，单源 bfs 就是每次从一个源头开始进行 bfs，结束后又从另一个源头开始。

如果本题按照单源 bfs 来做，那就是遇到每一个 1 都开始 bfs，直到遇到0返回，最坏时间复杂度有 ，超时了。

所以要用多源 bfs，将所有0作为源头（不用1，因为0比较方便，可以将0看作病毒），然后加入到队列中做源头，然后取出每一个源头，如果遇到了 -1 则感染它（为了防止重复，所有1的地方都置为-1），然后不断扩散。思路跟橘子感染的思路差不多。

3、代码

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<int[]> queue = new LinkedList<>();

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j] == 0){
                    queue.offer(new int[]{i, j});
                }else{
                    mat[i][j] = -1;
                }
            }
        }

        int step = 1;
        while(!queue.isEmpty()){
            int size = queue.size();

            for(int i = 0; i < size; i++){
                int[] index = queue.poll();
                int row = index[0], column = index[1];
                
                for(int[] direct : direction){
                    int newRow = direct[0] + row, newColumn = direct[1] + column;
                    if(newRow < 0 || newRow >= m || newColumn < 0 || newColumn >= n || mat[newRow][newColumn] >= 0){
                        continue;
                    }
                    mat[newRow][newColumn] = step;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
            step++;
        }

        return mat;
    }
}