问题：
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
输出:
示例 2:
输入:
输出:
思路
一看到这个题目就直接是想到用动态规划去写，先是找到问题的状态，比如0和1，然后有了更新状态的方式：当前点的左、上、右、下四个方向的dp值的最小值+1便是当前状态的值。
然而实际写的时候发现了问题，在更新dp值的时候，因为是逐行逐列的遍历，导致下边和右边的值无法获取（因为还没有遍历到）。其实之所以想到用动态规划是因为之前见过类似的题目，那个题目是限制只能向下和向右移动来更新dp值。
要解决这道题，要跳开思维限制，不追求一次遍历就得到结果，而是可以通过两次遍历，即：
- 第一次遍历从左上角出发，根据左边和上边的状态来更新dp值。
- 第二次遍历从右下角出发，根据左边和下边的状态来更新dp值。
也就是说，把这个问题转化为了2个具有不同限制的动态规划问题。
代码
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
30
31
| class Solution {
public int[][] updateMatrix(int[][] matrix) {
if(matrix == null){
return null;
}
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(matrix[i][j] == 0){
continue;
}
int left = i == 0 ? row + col : dp[i-1][j] + 1;
int top = j == 0 ? row + col : dp[i][j-1] + 1;
dp[i][j] = Math.min(left, top);
}
}
for(int i = row - 1; i >= 0; i--){
for(int j = col - 1; j >=0 ; j--){
if(matrix[i][j] == 0){
continue;
}
int right = j == col - 1 ? row + col : dp[i][j+1] + 1;
int below = i == row - 1 ? row + col : dp[i+1][j] + 1;
dp[i][j] = Math.min(dp[i][j], Math.min(right,below));
}
}
return dp;
}
}
|
这是原本的解法，没有改变传入的matrix数组的值。还有一种解法是直接在原数组上进行状态更新，我觉得这样虽然节省空间，但是改变了数组的值，不太优雅。如下所示：
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
30
31
32
33
34
35
| class Solution {
private int row;
private int col;
public int[][] updateMatrix_1(int[][] matrix) {
row = matrix.length;
col = matrix[0].length;
// 第一次遍历，正向遍历，根据相邻左元素和上元素得出当前元素的对应结果
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = row + col;
}
if (i > 0) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i - 1][j] + 1);
}
if (j > 0) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][j - 1] + 1);
}
}
}
// 第二次遍历，反向遍历，根据相邻右元素和下元素及当前元素的结果得出最终结果
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i < row - 1) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i + 1][j] + 1);
}
if (j < col - 1) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][j + 1] + 1);
}
}
}
return matrix;
}
}
|
追求可读性，则代码往往很丑，想要写的简洁则可读性又会降低。想写出优雅的代码真的太磨人了。