LeetCode刷题【542】01矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

输出：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

示例 2：

输入：
[[0,0,0],
 [0,1,0],
 [1,1,1]]

输出：
[[0,0,0],
 [0,1,0],
 [1,2,1]]

提示：

• 给定矩阵的元素个数不超过 10000。
• 给定矩阵中至少有一个元素是 0。
• 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

题解

import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;

        Queue<int[]> list = new LinkedList<>();
        boolean[][] visited = new boolean[row][col];
        int[][] dist = new int[row][col];
        for (int i = 0; i <= row - 1; i++) {
            for (int j = 0; j <= col - 1; j++) {
                if (mat[i][j] == 0){
                    list.offer(new int[]{i,j});
                    visited[i][j] = true;
                }
            }
        }

        int [][] move = {{-1,0}, {1,0},{0,1},{0,-1}};

        while (!list.isEmpty()){
            int[] item = list.poll();
            for (int[] targetPosition : move) {
                int[] target = {item[0]+targetPosition[0],item[1]+targetPosition[1]};
                if (target[0]<0 || target[0]> row-1 || target[1]<0 || target[1] >col-1  || visited[target[0]][target[1]]) {
                    continue;
                }
                dist[target[0]][target[1]] = dist[item[0]][item[1]] + 1;
                list.offer(target);
                visited[target[0]][target[1]] = true;

            }
        }

        return dist;
    }
}

题解2：动态规划

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;

        int bigValue = (Integer.MAX_VALUE-1) >> 1;
        int[][] dist = new int[row][col];
        for (int i = 0; i <= row - 1; i++) {
            for (int j = 0; j <= col - 1; j++) {
                if (mat[i][j] == 0){
                    dist[i][j] = 0;
                }else{
                    dist[i][j] = bigValue;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dist[i][j] == 0){
                    continue;
                }
                getMin(dist,i,j);
            }
        }
        for (int i = row-1; i >=0; i--) {
            for (int j = col-1; j >= 0; j--) {
                if (dist[i][j] == 0){
                    continue;
                }
                getMin(dist,i,j);
            }
        }

        return dist;
    }


    private static void getMin(int[][] dist ,int i, int j){
        if (i-1>=0){
            dist[i][j] = Math.min(dist[i][j],dist[i-1][j]+1);
        }
        if (j-1>=0){
            dist[i][j] = Math.min(dist[i][j],dist[i][j-1]+1);
        }
        if (i+1 < dist.length){
            dist[i][j] = Math.min(dist[i][j],dist[i+1][j]+1);
        }
        if (j+1 < dist[0].length){
            dist[i][j] = Math.min(dist[i][j],dist[i][j+1]+1);
        }
    }
}