Simple BFS idea


  • 0

    modified to be more concise

    public class Solution {
        private int[][] dirs = {{1,0},{-1,0},{0,-1},{0,1}};
        private int m, n;
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            List<List<Integer>> res = new ArrayList<>();
            if (matrix == null || matrix.size() == 0 || matrix.get(0).size() == 0) return res;
            m = matrix.size();
            n = matrix.get(0).size();
            boolean[][] visited = new boolean[m][n]; 
    
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix.get(i).get(j) == 0) {
                        visited[i][j] = true;
                        queue.offer(new int[]{i, j});
                    }
                }
            }
            
            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                for (int[] dir : dirs) {
                    int nx = curr[0] + dir[0], ny = curr[1] + dir[1];
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[nx][ny]) continue;
                    visited[nx][ny] = true;
                    int dist = matrix.get(curr[0]).get(curr[1]);
                    matrix.get(nx).set(ny, dist + 1);
                    queue.offer(new int[]{nx, ny});
                }
            }
            return matrix;
        }
    }
    

    [old version] not concise since I treat the input matrix as immutable.

    public class Solution {
        private int[][] dirs = {{1,0},{-1,0},{0,-1},{0,1}};
        private int m, n;
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            List<List<Integer>> res = new ArrayList<>();
            if (matrix == null || matrix.size() == 0 || matrix.get(0).size() == 0) return res;
            m = matrix.size();
            n = matrix.get(0).size();
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                res.add(new ArrayList<Integer>());
                for (int j = 0; j < n; j++) {
                    res.get(i).add(0);
                }
            }
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (valid(matrix, i, j)) {
                        visited[i][j] = true;
                        queue.offer(new int[]{i, j});
                    }
                }
            }
            int dist = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                dist++;
                for (int i = 0; i < size; i++) {
                    int[] point = queue.poll();
                    res.get(point[0]).set(point[1], dist);
                    for (int[] dir : dirs) {
                        int nx = point[0] + dir[0];
                        int ny = point[1] + dir[1];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix.get(nx).get(ny) == 1 && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
            return res;
        }
        private boolean valid(List<List<Integer>> matrix, int i, int j) {
            if (matrix.get(i).get(j) == 0) return false;
            else {
                if (i > 0 && matrix.get(i - 1).get(j) == 0) return true;
                if (i < m - 1 && matrix.get(i + 1).get(j) == 0) return true;
                if (j > 0 && matrix.get(i).get(j - 1) == 0) return true;
                if (j < n - 1 && matrix.get(i).get(j + 1) == 0) return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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