问题:

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。

示例 1: 输入:

1
2
3
0 0 0
0 1 0
0 0 0

输出:

1
2
3
0 0 0
0 1 0
0 0 0

示例 2: 输入:

1
2
3
0 0 0
0 1 0
1 1 1

输出:

1
2
3
0 0 0
0 1 0
1 2 1

思路

​ 一看到这个题目就直接是想到用动态规划去写,先是找到问题的状态,比如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;
    }
}

追求可读性,则代码往往很丑,想要写的简洁则可读性又会降低。想写出优雅的代码真的太磨人了。