Easy BFS solution


  • 0
    C
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            int m=matrix.size(); if (m==0) return new ArrayList<>();
            int n=matrix.get(0).size(); if (n==0) return new ArrayList<>();
            int[][] ans=new int[m][n];
            for (int i=0;i<m;i++)
                for (int j=0;j<n;j++)
                    ans[i][j]=Integer.MAX_VALUE;
            Queue<Integer> queue=new LinkedList<>();
            for (int i=0;i<m;i++) {
                for (int j=0;j<n;j++) {
                    if (matrix.get(i).get(j)==0) {
                        ans[i][j]=0;
                        queue.offer(i);
                        queue.offer(j);
                    }
                }
            }
            while (!queue.isEmpty()) {
                int x=queue.poll(), y=queue.poll(), d=ans[x][y];
                for (int[] dir: new int[][] {{1,0},{-1,0},{0,1},{0,-1}}) {
                    int xx=x+dir[0], yy=y+dir[1];
                    if (xx>=0 && xx<m && yy>=0 && yy<n && ans[xx][yy]>d+1) {
                        ans[xx][yy]=d+1;
                        queue.offer(xx);
                        queue.offer(yy);
                    }
                }
            }
            return Arrays.stream(ans)
                    .map(i->Arrays.stream(i).boxed().collect(Collectors.toList())).collect(Collectors.toList());
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.