給定一個由 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。
矩陣中的元素只在四個方向上相鄰: 上、下、左、右。

代碼：

方法一：動態規劃

class?Solution?{

????public?int[][]?updateMatrix(int[][]?matrix)?{

????????

????????int?dp[][]?=?new?int[matrix.length][matrix[0].length];

????????if(matrix.length==0){

????????????return?dp;

????????}

????????for(int?i=0;i<matrix.length;i++){

????????????for(int?j=0;j<matrix[0].length;j++){

????????????????if(matrix[i][j]==1){

????????????????????dp[i][j]=matrix.length+matrix[0].length;

????????????????}

????????????}

????????}

????????for(int?i=0;i<matrix.length;i++){

????????????for(int?j=0;j<matrix[0].length;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=matrix.length-1;i>=0;i--){

????????????for(int?j=0;j<matrix[0].length;j++){

????????????????if(i<matrix.length-1){

????????????????????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=matrix.length-1;i>=0;i--){

????????????for(int?j=matrix[0].length-1;j>=0;j--){

????????????????if(i<matrix.length-1){

????????????????????dp[i][j]?=?Math.min(dp[i][j],dp[i+1][j]+1);

????????????????}

????????????????if(j<matrix[0].length-1){

????????????????????dp[i][j]?=?Math.min(dp[i][j],dp[i][j+1]+1);

????????????????}

????????????}

????????}

????????for(int?i=0;i<matrix.length;i++){

????????????for(int?j=matrix[0].length-1;j>=0;j--){

????????????????if(i>0){

????????????????????dp[i][j]?=?Math.min(dp[i][j],dp[i-1][j]+1);

????????????????}

????????????????if(j<matrix[0].length-1){

????????????????????dp[i][j]?=?Math.min(dp[i][j],dp[i][j+1]+1);

????????????????}

????????????}

????????}

????????return?dp;

????}

}

方法二：BFS

class?Solution?{

????int[][]?vector?=?new?int[][]{{0,1},{0,-1},{1,0},{-1,0}};

????public?int[][]?updateMatrix(int[][]?matrix)?{

????????if(matrix.length==0){

????????????return?matrix;

????????}

????????Queue<int[]>?queue?=?new?LinkedList<>();

????????for(int?i=0;i<matrix.length;i++){

????????????for(int?j=0;j<matrix[0].length;j++){

????????????????if(matrix[i][j]==1){

????????????????????matrix[i][j]=matrix.length+matrix[0].length;

????????????????}else{

????????????????????queue.add(new?int[]{i,j});

????????????????}

????????????}

????????}

????????while(!queue.isEmpty()){

????????????int?[]s?=?queue.poll();

????????????for(int[]?v:vector){

????????????????int?r?=?s[0]+v[0],c=s[1]+v[1];

????????????????if(r>=0&&r<matrix.length&&c>=0&&c<matrix[0].length&&matrix[s[0]][s[1]]+1<matrix[r][c]){

????????????????????matrix[r][c]?=?matrix[s[0]][s[1]]+1;{

????????????????????queue.add(new?int[]{r,c});

????????????????}

????????????}

????????}

????}

????return?matrix;

????}

}

總結

以上是生活随笔為你收集整理的Leetcode--542. 01 矩阵(java)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。