542. 01 Matrix

Posted on | Edited on | Views: 1

LeetCode

link
BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        Queue<int[]> queue=new LinkedList<>();
        int R=matrix.length,C=matrix[0].length;
        boolean[][] visited=new boolean[R][C];
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(matrix[i][j]==0){
                    visited[i][j]=true;
                    queue.offer(new int[]{i,j});
                }
            }
        }
        int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}};
        while(!queue.isEmpty()){
            int[] pos=queue.poll();
            for(int[] d:dirs){
                int newX=pos[0]+d[0];
                int newY=pos[1]+d[1];
                if(newX<0||newX>=R||newY<0||newY>=C||visited[newX][newY]) continue;
                visited[newX][newY]=true;
                matrix[newX][newY]=matrix[pos[0]][pos[1]]+1;
                queue.offer(new int[]{newX,newY});
            }
        }
        return matrix;
    }
}

0%