【LeetCode】542. 01 矩阵(BFS)

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

示例 1:
输入:

0 0 0
0 1 0
0 0 0

输出:

0 0 0
0 1 0
0 0 0

示例 2:
输入:

0 0 0
0 1 0
1 1 1

输出:

0 0 0
0 1 0
1 2 1

注意:

• 给定矩阵的元素个数不超过 10000。
• 给定矩阵中至少有一个元素是 0。
• 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法一：BFS

将每个不为0的点进行BFS，寻找到0的距离

class Solution {
    int rows;
    int cols;
    int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    public int[][] updateMatrix(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(matrix[i][j] != 0){
                    matrix[i][j] = bfs(i,j,matrix);
                }
            }
        }
        return matrix;
    }
    public int bfs(int i, int j, int[][] matrix){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        int depth = 0;
        boolean flag = false;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int a = 0; a < size; a++){
                int[] node = queue.poll();
                for(int b = 0; b < 4; b++){
                    int newx = node[0] + dir[b][0];
                    int newy = node[1] + dir[b][1];
                    if(newx < 0 || newy < 0 || newx >= rows|| newy >= cols) continue;
                    if(matrix[newx][newy] == 0){
                        flag = true;
                        break;
                    }
                    queue.add(new int[]{newx, newy});
                }
            }
            depth++;
            if(flag) break;
        }
        return depth;
    }
}

解法二：BFS

将所有为0的点压入队列，多源BFS
待补充

解法三：DP