PattySung

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]] Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]

<解題> 1.用BFS


class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 表示四個方向

        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});
                    visited[i][j] = true;
                } else {
                    matrix[i][j] = m + n;
                }
            }
        }

        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                for (int[] dir : dirs) {
                    int x = curr[0] + dir[0];
                    int y = curr[1] + dir[1];

                    if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) continue;

                    matrix[x][y] = step;
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y});
                }
            }
            step++;
        }

        return matrix;
    }
}

Time：O(MN) Space：O(MN)

<解題> 2.用DP


class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];

        for (int i =0; i< m; i++){
            for (int j=0; j<n; j++){
                if(matrix[i][j]==0){
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = m + n;
                }
            }
        }

        // 左上至右下
        for (int i =0; i< m; i++){
            for (int j=0; j<n; j++){
                if (i != 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);
                }
                if (j != 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);
                }
            }
        }

        // 右下至左上
        for (int i = m-1 ; i >=0; i--){
            for (int j = n-1 ; j >=0; j--){
                if (i != m-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j] + 1);
                }
                if (j != n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1] + 1);
                }
            }
        }

        return dp;
    }
}

Leetcode-542. 01 Matrix

<解題> 1.用BFS

<解題> 2.用DP