来自Leetcode第542题01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 2:
输入:
输出:
BFS
首先把每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ），扩散的时候可以设置 boolean[][] visited 标志是否访问过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length,col = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] seen = new boolean[row][col];
int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(int i = 0 ; i < row ; ++i){
for(int j = 0 ; j < col ; ++j){
if(matrix[i][j] == 0){
seen[i][j] = true;
queue.add(new int[]{i,j});
}
}
}
int[] tmp;
int dx,dy;
while (!queue.isEmpty()){
tmp = queue.poll();
for(int k = 0 ; k < 4 ; ++k){
dx = tmp[0]+d[k][0];
dy = tmp[1]+d[k][1];
if(dx >= 0 && dx < row && dy >= 0 && dy < col && !seen[dx][dy]){
matrix[dx][dy] = matrix[tmp[0]][tmp[1]] + 1;
queue.offer(new int[]{dx,dy});
seen[dx][dy] = true;
}
}
}
return matrix;
}
|
动态规划
用dp[i][j]表示该位置距离最近的0的距离，则dp[i][j] = 1+min(dp[i-1][j],dp[i][j-1],dp[i+1][j],dp[i][j+1]) if matrix[i][j] == 1
尝试将问题分解：
- 距离 (i, j) 最近的 0 的位置，是在其 「左上，右上，左下，右下」4个方向之一；
- 因此我们分别从四个角开始递推，就分别得到了位于「左上方、右上方、左下方、右下方」距离 (i, j)的最近的 0 的距离，取 min即可；
- 通过上两步思路，我们可以很容易的写出 4 个双重 for循环，动态规划的解法写到这一步其实已经完全 OK 了；
- 如果第三步还不满足的话，从四个角开始的4次递推，其实还可以优化成从任一组对角开始的2次递推，比如只写从左上角、右下角开始递推就行了。
对dp数组初始化时不能将其设置为0X7FFFFFFF，不然+1就会溢出，变成-2147483647.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length,col = matrix[0].length;
int[][] dp = new int[row][col];
for(int i = 0 ; i < row ; ++i)
for(int j = 0 ; j < col ; ++j)
dp[i][j] = matrix[i][j] == 0 ? 0 : 10000;
for(int i = 0 ; i < row ; ++i){
for (int j = 0 ; j < col ; ++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 = row - 1 ; i >= 0 ; --i){
for(int j = col - 1 ; j >= 0 ; --j){
if(i < row - 1)
dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
if(j < col - 1)
dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);
}
}
return dp;
}
|