原题
给定一个由 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/
