0x01.问题
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
示例：
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
public int[][] updateMatrix(int[][] matrix)
0x02.分析思路
读题，发现问题的要点在于找出1到附近0的最近距离。
毫无疑问，采用BFS，并且对于这种对每个点都需要找距离的问题来说，使用多源BFS是最合适的。
- 把所有的0的点作为BFS的第一层。
- 将1都初始化为
Integer.MAX_VALUE，省去了一个标记数组的空间。 - 对队列中每一个元素，如果下一个点满足条件且，下一个点的值为
Integer.MAX_VALUE，就设置下一点的值为当前点的值加1。
0x03.解决代码–多源BFS
class Solution {
public int[][] updateMatrix(int[][] matrix) {
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int m=matrix.length;
int n=matrix[0].length;
Queue<int[]> queue=new LinkedList<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0){
queue.add(new int[]{i,j});
}else{
matrix[i][j]=Integer.MAX_VALUE;
}
}
}
while(!queue.isEmpty()){
int arr[]=queue.poll();
for(int i=0;i<4;i++){
int nx=arr[0]+dx[i];
int ny=arr[1]+dy[i];
if(nx<0||ny<0||nx==m||ny==n) continue;
if(matrix[nx][ny]!=Integer.MAX_VALUE) continue;
matrix[nx][ny]=matrix[arr[0]][arr[1]]+1;
queue.add(new int[]{nx,ny});
}
}
return matrix;
}
}
愿未来你所珍惜，值你珍惜。
ATFWUS --Writing By 2020–04–15
1541
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
