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
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int[][] result = new int[mat.length][mat[0].length];
        initialize(result);
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                helper(mat, result, i, j);
            }
        }
        return result;
    }

    private void initialize(int[][] result) {
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                result[i][j] = -1;
            }
        }
    }

    private int helper(int[][] mat, int[][] result, int row, int col) {
        if (isOutOfBound(mat, row, col) || result[row][col] == -2) {
            return Integer.MAX_VALUE;
        }
        if (result[row][col] == -1 && mat[row][col] == 0) {
            result[row][col] = 0;
            return result[row][col];
        }
        if (result[row][col] != -1)
            return result[row][col];

        result[row][col] = -2;
        int up = helper(mat, result, row - 1, col);
        int down = helper(mat, result, row + 1, col);
        int left = helper(mat, result, row, col - 1);
        int right = helper(mat, result, row, col + 1);
        int minimum = Math.min(Math.min(left, right), Math.min(up, down)) + 1;
        result[row][col] = minimum;
        return result[row][col];
    }

    private boolean isOutOfBound(int[][] mat, int row, int col) {
        return row < 0 || row >= mat.length || col < 0 || col >= mat[0].length;
    }
}

上面是我使用DFS失败的尝试. 我发现走到最后很可能进入了一个死胡同, 就是上和右都是来的时候走过的路, 下是边界, 而从左回来到达这个点. 那么此时这个点的minimum distance to the closest 0可以确定吗? 此时是无法确定的. 然而我的逻辑却是错误地取周围块儿的值中的最小的, 然而此时它们可能也没得到自己的最小值是多少. 这道题感觉使用DFS就是在我们是边走边记录走过的地方, 然后不能往之前走过的地方再去走. 有些路可能到一定地方就没办法确定. 因为周围的格子它们的
最小distance也许也不确定(比如是我们来的路上经过的格子, 还等着我们返回结果呢). 于是就出现了问题.

现在的问题时, 如何以后做题识别到这类问题呢? 就是DFS会出现这种情况. 我现在觉得是看特殊条件, 这道题返回给我们的东西要么是确实是minimum distance要么就是因为出界或者走回头路而给我们Integer.MAX_VALUE, 也就是当我们收到Integer.MAX_VALUE的时候, 有可能是出界, 有可能是走回头路, 那如何分辨呢? 于是这就出现问题了. 还有就是即使分辨了, 也没用啊.

我又发现关键问题就是互相依赖. 想知道一个格子的最小距离, 那得知道周围的格子的最小距离. 周围格子比如上方的那个, 想要知道它的, 也需要知道它的周围格子, 这又会跳回我们之前的格子. 等于是之前格子需要知道上方格子的最小距离而知道上方格子的最小距离还要知道之前格子的最小距离, 这就出现了互相依赖的情况.我们在写逻辑的时候发现会出现上下来回反复的情况, 比如进入一个格子, 然后调用上方格子, 上方格子由于是到顶了, 于是会调用下方, 之后下方又会调用上方, 这样来回反复. 因此我们是不让走回头, 从而防止陷入死循环, 也就是防止上下来回调换导致overflow. 但我们没有意识到这个做法还导致了我们的逻辑出现了严重漏洞. 这就导致逻辑出现了问题. 我们这样做会强制认为上方格子不可能通过之前的格子达到最小(通过走回头路的直接返回Integer.MAX_VALUE), 等于是还是递归函数的逻辑出现了问题. 递归函数的逻辑违反了我们之前的知道四个方向格子的最小距离后得到其中最小的假设. 我们的逻辑则是知道四周没走过的格子的最小距离然后取最小, 强制认为不可能从之前走过的路达到最小距离.

我当时是从以下这个input发现问题的:
[[1,0,1,1,0,0,1,0,0,1],
[0,1,1,0,1,0,1,0,1,1],
[0,0,1,0,1,0,0,1,0,0],
[1,0,1,0,1,1,1,1,1,1],
[0,1,0,1,1,0,0,0,0,1],
[0,0,1,0,1,1,1,0,1,0],
[0,1,0,1,0,1,0,0,1,1],
[1,0,0,0,1,1,1,1,0,1],
[1,1,1,1,1,1,1,0,1,0],
[1,1,1,1,0,1,0,0,1,1]]

这个是运行到一半时, result这个二维数组的样子.
[[1,0,1,1,0,0,1,0,0,1],
[0,1,1,0,-2,0,1,0,1,1],
[-1,0,1,0,-2,-1,0,-1,0,0],
[-1,0,1,0,-2,-1,-1,-1,-1,-1],
[-1,-1,0,-1,-2,0,-1,-1,-1,-1],
[-1,-1,-1,0,-2,-2,-1,-1,-1,-1],
[0,-1,-1,-1,0,-2,-1,-1,-1,-1],
[1,0,0,0,1,-2,-1,-1,-1,-1],
[2,-2,-2,-2,-2,-2,-1,-1,-1,-1],
[3,-2,-2,-2,0,1,0,-1,-1,-1]]

上面这个case就是我们逻辑漏洞的体现. 看最后一行的左边第二个. 此时递归函数在这个位置, 并且刚从left返回. 此时根据我们的逻辑, 我们接下来要走右侧, 此时发现是-2, 意味着我们路过这里过, 因此返回给我们Integer.MAX_VALUE. 至此, 上下左右都调用完毕, 上下右的min值是Integer.MAX_VALUE, 左是3, 那么这就意味着最后一行左二这个位置的最小距离就是3 + 1 = 4吗? 当然不是. 我们的上右两个格子的最小距离都还没确定.但我们的逻辑则强行认为左就是最小的. 我们的逻辑是只要出界和走之前走过的路就会返回Integer.MAX_VALUE, 通过这个值来告诉我们不可能从这些格子达到最小值. 然而碰巧的是, 这个位置(最后一行左二)恰好是从上方格子达到最小值的.

总的来说就是我们要保证我们的递归函数做的事情是符合我们当初假设它会干的事情的. 这个要保持一致.

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
36
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[] { i, j });
                } else {
                    mat[i][j] = -1;
                }
            }
        }

        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        while (!queue.isEmpty()) {
            int[] currentPair = queue.poll();
            for (int[] direction : directions) {
                int neighborRow = currentPair[0] + direction[0];
                int neighborCol = currentPair[1] + direction[1];
                // Not out of bound and haven't been visited
                if (!isOutOfBound(mat, neighborRow, neighborCol) &&
                        mat[neighborRow][neighborCol] != -1) {
                    mat[neighborRow][neighborCol] = mat[currentPair[0]][currentPair[1]] + 1;
                    queue.offer(new int[] { neighborRow, neighborCol });
                }
            }
        }
        return mat;

    }

    private boolean isOutOfBound(int[][] mat, int row, int col) {
        return row < 0 || row >= mat.length || col < 0 || col >= mat[0].length;
    }
}

上面这个方法就直接明了了. 首先我们找到所有一开始是0的格子, 那么很容易知道这些格子的最小距离就是0. 之后我们从这些是0的格子出发找它们的邻居, 注意如果邻居格子的最小距离已经确定就不打扰了, 目前为止这类格子就是刚才的本身就是0的格子. 那么很容易确定这些之前最小距离还没确定的邻居的最小距离就是1, 因为它们本身不是0但又挨着0, 于是一定是1. 然后再看这些最小距离是1的格子它们周围的还没更新最小距离的邻居. 直到所有的格子都被填上正确的最小距离. 这个思路就是BFS. 首先是从0处格子出发, 把自己所有的邻居走一遍, 之后从这些邻居出发再把它们的邻居走一遍(不包含已经确定最小距离的邻居). 以此类推.

先把所有等于0的格子的位置存起来. 然后把1的位置初始化为-1代表着该处格子到最近0的距离还未确定. 此时第一遍把所有和0挨着的格子中还未确定距离的统一标记为1. 因为这些格子本身不是0但又挨着1, 于是最近0的距离一定是1. 然后再把它们的邻居中未确定距离的格子压进去. 到了某个时刻所有是0的格子全部被遍历完, 此时开始看距离是1的格子, 现在统一把它们的邻居中未确定距离的标记为2. 因为这些格子没有确定距离, 也就是本身不是0, 其次还不挨着0(如果挨着, 那么此时肯定被标记为1而非未确定状态), 那么它们距离0的距离一定大于1, 但是挨着距离最近0是1的格子, 那么无疑它们距离0最近的距离就是2, 这也是它们能取到到0距离范围中最小的值(自己不是0, 还不挨着0, 那么到0的距离大于等于2). 这样以此类推.

于是我们可以用队列来存, 开始是把所有的0存进去, 然后挨个pop出来看它们的邻居. 更新好邻居的最小距离的同时把这些邻居也压入queue. 从而让我们之后看这些邻居的邻居. 以此类推. 那么如何避免走之前更新过值的格子呢? 也就是如何区分还没有确定距离的和那些已经确定好距离的邻居呢? 那就是刚开始第一遍遍历整个二维数组的时候, 在把格子是0的这些格子的坐标装进queue的同时, 我们把不是0的格子标记成-1, 代表着它们的最小距离还没有确定. 然后在我们更新的时候只去更新是-1的格子, 如果一个格子上不是-1, 那就说明它们的距离已经确定好. 到此, 这个逻辑就结束了. 由于我们是先从是0的格子的邻居入手(本身不是0的邻居), 它们的最小距离一定是正确的. 然后再从这些邻居出发看他们的邻居. 它们的邻居一定不和0挨着(否则上一步就会被更新), 但是却和最小距离是1的格子挨着, 于是它们的最小距离是2. 然后看是2的格子的周围的邻居, 如果它们和是0或1的格子挨着, 那么它们一定在上上步或上一步就被更新, 但是没有. 于是它们和是2的格子挨着, 那么它们的最小距离一定是3. 以此类推. 因此每次只要确定一个格子的最小距离, 那么它们的值一定是对的.

时间复杂度: O(row * col)
空间复杂度: O(1)

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
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int numOfRow = mat.length, numOfCol = mat[0].length;
        int maximum = 100000;
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0)
                    continue;
                int up = maximum, left = maximum;
                if (i - 1 >= 0)
                    up = mat[i - 1][j];
                if (j - 1 >= 0)
                    left = mat[i][j - 1];
                mat[i][j] = Math.min(up, left) + 1;
            }
        }

        for (int row = numOfRow - 1; row >= 0; row--) {
            for (int col = numOfCol - 1; col >= 0; col--) {
                if (mat[row][col] == 0)
                    continue;
                int right = maximum, down = maximum;
                if (col + 1 < numOfCol)
                    right = mat[row][col + 1];
                if (row + 1 < numOfRow)
                    down = mat[row + 1][col];
                mat[row][col] = Math.min(Math.min(right, down) + 1, mat[row][col]);
            }
        }
        return mat;
    }
}

这个方法就是动态规划. 可以这么想, 从左上角开始遍历整个数组. 我们第一遍假设只能往上或者往左走到达最近的0. 那么从左上角开始, 一直往后遍历, 到达每个格子先看自己是不是0, 是0的话那最短距离肯定就是0. 如果不是, 我们就要看从左边走近还是从上边走近. 这时要考虑上边和左边可能出界的问题. 如果上面或左边出界那就给一个特别大的值来表示出界. 之后我们看哪边走最近. 有可能是两边都是出界就比如左上角那个格子, 此时这个格子的最短距离就是特别大的值, 代表目前无法确定. 这样我们到一个格子, 我们就能知道左边和上边格子到0的最短距离因为我们之前是路过它们并且寻找过它们各自到达0的最短距离的, 此时要记得我们是假设只能往上或者往左走到达最近的0. 中途不能往右或者往下. 此时如果我们遍历完所有的格子, 我们能得到所有格子从自己出发只能向左或者向上的前提下的最短到0的距离.

走完之后, 只有右下角达到了最佳化(能确定). 因为距离它最近的只能是往上或者往左走, 当然它自己也可能是0.

之后我们再从右下角开始往左上角倒着遍历. 先从最后一行倒数第二个格子开始研究(右下角左边的那一个格子). 想象一个区域, 由它往左上方放射一个矩形区域. 这个区域中距离这个格子最近的0和它的距离就是当前这个格子的值. 毕竟是从左上角往下挨个遍历的. 那么剩下没被框起来的区域就只剩下它右侧的一列了. 于是, 此时距离这个格子最近的0只可能出现在这两个区域. 如果是在被框起来的区域, 那么答案就是这个格子的值, 如果在右侧, 那么如果从这个格子出发前往右侧区域距离它最近的0, 我们则一定会有向右走的动作, 不管什么时候, 一定会向右, 早晚都会的. 那么不如我们第一步就向右, 此时达到右下角那个格子. 我们知道的是这个格子能把我们带到距离它最近的0. 如果距离最后一行右二的最近的0在它的右侧区域, 那么这个0一定距离右下角这个格子更近. 假设我们取右侧中任何一个位置, 那么到达右下角的路线可以是朝着右下角所在列往下走就ok了(这个路线和其他路线走法虽然不同, 但是总的步数一定相同, 前提不往回走). 如果要到右二则还要往左一步. 因此假设距离右二最近的0在它的右侧, 那么先走一步到右一(右下角), 然后到距离右一最近的0就行了. 如果距离右二最近的0出现在它的左侧(或上侧), 那么它距离这个0一定比右一距离这个0要近, 证明方法还是像上面那样先走垂线, 再走到目的地. 此时我们需要比较的就是右二到左侧区域最近的0的距离(也就是当前格子的值)和右一到距离它最近的0的距离 + 1. 取小的即可. 如果右一的值 + 1更大, 这说明距离右二的最小0在它所框起来的区域; 否则就是在右二的右侧. 此时完成右二全局最近距离得到.

同样的道理, 距离右三最近的0如果在左上侧区域, 那么自己同行右边的格子(右二)往这个0走肯定要走更多步数. 如果这个最小0在右三的右侧, 那么此时这个最小0距离右二比距离右三要近. 证明是一样的道理. 从右三出发到这个右侧0在途中一定要向右走一步. 此时我们可以先到达右二, 由于右二已经全局最近. 那么直接去距离右二最近的0即可. 此时比较这两种情况哪个近, 是右三本来的值(距离框起来的区域中最小0的距离)还是右二最短距离 + 1(最小0在右三的右侧). 如果是右三存的的值小, 那么说明距离它最近的0在自己的左上侧; 否则就是在自己的右侧, 是通过右二到达的.

同理最后一行每个格子都可以按照这个思路获得全局最近.

此时来到倒数第二行. 最右侧的格子发散框起来的区域只有最后一行没有包含进去. 此时它存的值就是它到框起来的区域中距离它最近的0的距离(如果有的话). 此时另外一种情况就是距离它最近的0在它的下面. 一样的道理, 如果确实是在下方, 它下面一格(右下角)一定比它要距离这个0近, 证明方法一样, 在这个区域随便取一个格子, 往倒数第二行最右侧那一列作垂线, 先往这个方向走, 然后再往上, 此时一定先路过下面这个格子, 然后才路过它. 于是我们可以先往下走一格, 然后去最近的0即可. 此时比较自己格子存的值(到左上区域最近的0的距离)和从下面一个格子然后到它最近0的距离 + 1(检验是否0在下面的区域). 如果自己格子存的值小, 那么说明在左上, 否则就是在下方.

然后来到倒数第二行倒数第二个. 一样的道理, 如果这个最小0在它的右侧, 那么往右走一格(总得向右走)然后去最近的0即可. 此时一定比到该格子的距离近. 同时如果假设这个最小0在下侧, 那么就先向下一步(总得向下), 到达下面一格, 然后从这里走到最近的0即可. 当然最小0可能出现在自己的左上侧. 比较这三者的距离, 得到最小的即可. 出现在右侧的话, 这个最小0一定距离自己右边的格子更近, 出现在下侧的话一定距离自己下面的格子更近. 如果出现右侧格子最短距离 + 1或者下侧格子最短距离 + 1大于自己本来存的值, 这就说明这个最小0不在右侧或者下侧而是在自己的左上侧, 也就是自己本来存的这个值.

本质就是如果不在自己的左上侧, 假设在右侧, 那么通过右边一个格子走到右边这个格子最近的0即可. 假设在下侧, 则通过下边一个格子走到下边这个格子最近的0即可. 因为在右侧, 我们总要向右走, 先走后走都不会影响总的步数. 同理, 下侧也是一定要往下走. 于是我们直接到右侧格子或者下侧格子出发.

有没有最小0在右侧, 但是这个最小0距离自己比距离自己右侧这个格子更近? 不可能. 证明方法之前提过. 右侧随便一个格子到我们这个格子的距离可以分为竖直要走的步数 + 水平走的步数. 由于自己这个格子和我们右侧格子在同一行, 因此竖直步数相同. 又由于右侧格子比我们靠右, 因此水平距离上右侧格子一定比我们距离这个随机格子的水平距离要近. 因此, 只要是出现在右侧的最小0, 它已经距离我们右侧的格子更近. 不必担心它们给我们领到右侧更远的一个地方. 下侧的情况同理. 这也是我们为什么要比较两次, 右边是为了看一看有没有可能最小0在右边, 下侧则是判断有没有可能在下边.

我们右侧的格子它的最小0也是要么分布在左上, 要么右侧(包含自己所在这一列), 要么下侧. 如果在左侧一定比我们的值小,在下侧不好说. 但是我们下侧的判定不通过它. 如果真是下侧, 下侧格子到这个点的距离和右侧格子到这里的距离要么相等, 要么比它小(通过画图可以证明, 同样在右侧格子下侧随便取点, 然后比较). 更不用说从下侧格子出发到右侧格子下方区域的最小0可能更近. 也就是假设右侧格子的最小0在它的下侧, 那么下侧格子到这个最小0的距离是小于等于右侧格子到它的最小0的距离的. 同时下侧格子的最小0到下侧格子的距离还可能更小.因此下侧情况留给我们查看下侧格子最小0距离的时候去检查. 在右侧 + 1后不好说, 但它一定会带我们去最近的(从我们这个位置走一步后能到达的最近的0), 否则只可能是右侧格子没达到全局最近, 这也和我们已知条件相悖.

相同的, 下侧的格子也是分为这三个区域. 左上, 右侧, 下侧(包含自己所在的这一行). 在左侧则一定比我们的值大, 在右侧则是右侧格子到该最小0的距离是小于等于下侧格子到自己的最小0的距离的, 更不用说右侧格子到自己的最小0可能更短. 这在刚才我们的检查中已经被记录好(右侧格子到自己的最小0的距离). 在下侧一定会带我们去最近的(从我们这个位置走一步后最近的0), 否则这个下侧格子也不是全局最短, 这同样和已知条件相悖.

这个DP逻辑大家都没说清楚. 我自己思考半天才意识到这个. 但是想明白就没事儿了.

时间复杂度: O(n)
空间复杂度: O(1)