leetcode542-01矩阵

彭晨涛 • 2019年12月13日 18:05 • 算法 • 阅读 7

原题

给定一个由 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。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法

思想

BFS：
先将所有0标记出，然后紧挨0未被标记出的就是1，标记所有1，紧挨1未被标记出的就是2……

动态规划：
依次遍历每个元素，如果四周有0就是1，如果没有也不是0就根据所有相邻元素对应的值中的最小值+1获得。

代码

BFS：

class Point{
    public int x;
    public int y;
    public Point(int x,int y){
        this.x = x;
        this.y = y;
    }
} 

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        int[][] marked = new int[height][width];
        int[][] ans = new int[height][width];
        Queue<Point> queue = new LinkedList<>();
        //将原二维数组中所有0答案设为0
        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(matrix[i][j] == 0){
                    marked[i][j] = 1;
                    ans[i][j] = 0;
                    queue.offer(new Point(i,j));
                }
            }
        }

        while(!queue.isEmpty()){
            Point point = queue.poll();
            if(point.x!=0 && marked[point.x-1][point.y]!=1){
                ans[point.x-1][point.y] = ans[point.x][point.y]+1;
                marked[point.x-1][point.y] = 1;
                queue.offer(new Point(point.x-1,point.y));
            } 
            if(point.x!=height-1 && marked[point.x+1][point.y]!=1){
                ans[point.x+1][point.y] = ans[point.x][point.y]+1;
                marked[point.x+1][point.y] = 1;
                queue.offer(new Point(point.x+1,point.y));
            } 
            if(point.y!=0 && marked[point.x][point.y-1]!=1){
                ans[point.x][point.y-1] = ans[point.x][point.y]+1;
                marked[point.x][point.y-1] = 1;
                queue.offer(new Point(point.x,point.y-1));
            } 
            if(point.y!=width-1 && marked[point.x][point.y+1]!=1){
                ans[point.x][point.y+1] = ans[point.x][point.y]+1;
                marked[point.x][point.y+1] = 1;
                queue.offer(new Point(point.x,point.y+1));
            }     
        }
        return ans;
    }
}

动态规划：

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++){
                dp[i][j] = dfs(matrix, dp, i, j);
            }
        }
       return dp;     
    }
    public static int dfs(int[][] matrix,int[][] dp, int i, int j){
        int m = matrix.length ;
        int n = matrix[0].length;
        if(i<0 || i>m-1 || j < 0 || j > n-1) return 9999;
        // 如果自身是0
        if(matrix[i][j] == 0) return 0;
        // 如果四周有0
        if(i > 0 && matrix[i-1][j] == 0) return 1;
        if(j < n-1 && matrix[i][j+1] == 0) return 1;
        if(i < m-1 && matrix[i+1][j] == 0) return 1; 
        if(j>0 && matrix[i][j-1] == 0) return 1;
        // 如果四周没有0根据四周的dp最小值+1获取
        int left,bottom,right,top;
        left=top=9999;

        if(i > 0 && dp[i-1][j] != 0){
            top = dp[i-1][j];
        }
        if(j> 0 && dp[i][j-1] != 0){
            left = dp[i][j-1];
        }
        bottom = dfs(matrix, dp,i+1, j);
        right = dfs(matrix, dp,i,j+1);
        return Math.min(Math.min(left, right), Math.min(top,bottom))+1; 
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode542-01%e7%9f%a9%e9%98%b5/

leetcode542-01矩阵

原题

解法

思想

代码

相关推荐

发表回复