1、前言

2、思路

使用多源 bfs，但是要注意的是，这里是找到0距离1最大的距离，源头是0开始肯定不对，因为0到1才有距离。所以源头应该从1开始，然后不断叠加 step 即可。

3、代码

class Solution {
    public int maxDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i, j});
                }else{
                    grid[i][j] = -1;
                }
            }
        }
        if(queue.size() == 0 || queue.size() == m * n){
            return -1;
        }

        int step = 0;
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 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 = row + direct[0], newColumn = column + direct[1];
                    if(newRow < 0 || newRow >= m || newColumn < 0 || newColumn >= n || grid[newRow][newColumn] >= 0){
                        continue;
                    }
                    grid[newRow][newColumn] = step;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
            step++;
        }

        return step - 1;
    }
}