给定一个由0和1组成的矩阵，找出每个元素到最近的 0 的距离两个相邻元素间的距离为 1 。
快速浏览
- 超级原点
- 广度优先
- 分层计算
代码一览
队列被用于广度优先的存储，因为可以先进先出，又JAVA中Queue是个抽象类，所以使用实现该类的LinkedList。对于方向的控制，用两个数组bx\by来控制，显得更加清晰。
这题最主要的是需要想到用广度优先的搜索算法，代码具体实现比较简单。
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Queue< int[] > q = new LinkedList<>();
boolean[][] marked = new boolean[m][n];
int[][] ans = new int[m][n];
for(int i = 0; i < m; i ++) {//初始化
for(int j = 0; j < n; j ++) {
marked[i][j] = false;
if(matrix[i][j] == 0) {
marked[i][j] = true;
q.add(new int[]{i,j});
ans[i][j] = 0;
}
}
}
int[] bx = {0,1,0,-1};//方向矢量
int[] by = {1,0,-1,0};
while (!q.isEmpty()) {
int[] xy = q.poll();
int x = xy[0];
int y = xy[1];
for(int i = 0; i < 4; i ++) {
if( 0 <= x + bx[i] && x + bx[i] < m
&& 0 <= y + by[i] && y + by[i] < n
&& !marked[x + bx[i]][y + by[i]]) {// 周围的点未被标记
marked[x + bx[i]][y + by[i]] = true;
q.add(new int[]{x + bx[i],y + by[i]});
ans[x + bx[i]][y + by[i]] = ans[x][y] + 1;
}
}
}
return ans;
}
