542. 01 Matrix

Description

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

Solution

BFS, time O(m * n), space O(m * n)

跟"286. Walls and Gates"完全相同的解法。
注意，这道题用的是BFS level traversal，而非Dijikstra，所以需要在进队列的时候更新dis，而非出队列的时候！

class Solution {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return matrix;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dis = new int[m][n];
        for (int[] row : dis) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    dis[i][j] = 0;
                }
            }
        }
        
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int neighborDis = dis[pos[0]][pos[1]] + 1;
            
            for (int[] direction : DIRECTIONS) {
                int x = pos[0] + direction[0];
                int y = pos[1] + direction[1];
                // check isValid here! otherwise dis[x][y] might be broken
                if (x < 0 || x >= m || y < 0 || y >= n || dis[x][y] < Integer.MAX_VALUE) {
                    continue;
                }

                dis[x][y] = neighborDis;
                queue.offer(new int[] {x, y});
            }
        }
        
        return dis;
    }
}

DFS: TLE

DP, time O(mn), space O(mn)

也可以用DP来解，因为每个位置(i, j)的结果只依赖与它上下左右邻居到0的距离。

用两遍遍历即可解决啦。有一个坑是，由于后面会对邻居的dis加一进行比较，所以不能将dis[][]初始化成Integer.MAX_VALUE，会overflow的！

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return matrix;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dis = new int[m][n];
        for (int[] row : dis) {
            Arrays.fill(row, 10001);    // shouldn't use Integer.MAX_VALUE! Add cause overflow
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dis[i][j] = 0;
                    continue;
                }
                
                if (i > 0) {
                    dis[i][j] = Math.min(1 + dis[i - 1][j], dis[i][j]);
                }
                
                if (j > 0) {
                    dis[i][j] = Math.min(1 + dis[i][j - 1], dis[i][j]);
                }
            }
        }
        
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i < m - 1) {
                    dis[i][j] = Math.min(1 + dis[i + 1][j], dis[i][j]);
                }
                if (j < n - 1) {
                    dis[i][j] = Math.min(1 + dis[i][j + 1], dis[i][j]);
                }
            }
        }
        
        return dis;
    }
}