题目地址：
https://www.lintcode.com/problem/01-matrix/description
给定一个 m m m行 n n n列的 0 − 1 0-1 0−1矩阵 A A A，每次允许从每个点可以向四个方向走一步。问每个位置到离其最近的 0 0 0的距离是多少（该距离称为曼哈顿距离）。返回和 A A A相同规模的矩阵 B B B，使得 B [ i ] [ j ] B[i][j] B[i][j]是 A [ i ] [ j ] A[i][j] A[i][j]离其最近的 0 0 0的距离。题目保证矩阵至少有一个 0 0 0。
法1：动态规划。设 f [ i ] [ j ] f[i][j] f[i][j]是 A [ i ] [ j ] A[i][j] A[i][j]走到离它最近的 0 0 0的距离。我们采取的策略是遍历两次。先从左上到右下遍历，求出每个位置如果只允许向上和向左走的话，离它最近的 0 0 0的距离。那么有，如果 A [ i ] [ j ] = 0 A[i][j]=0 A[i][j]=0，那么 f [ i ] [ j ] = 0 f[i][j]=0 f[i][j]=0；如果 A [ i ] [ j ] = 1 A[i][j]=1 A[i][j]=1，那么要么是从上面走过来的，要么是从左边走过来的，所以以 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]和 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]对 f [ i ] [ j ] f[i][j] f[i][j]进行更新。当然第一次遍历的过程中可能有的点是无法走到 0 0 0的，可以标记成 m + n m+n m+n或者任何一个不合法的数字即可。接下来再从右下到左上遍历，以同样的理由以 f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j]和 f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1]对 f [ i ] [ j ] f[i][j] f[i][j]进行更新。最后所得的 f f f即为答案。
算法正确性证明：
反证法。如果对于某个 ( i , j ) (i,j) (i,j)，上述方法更新出来的 f [ i ] [ j ] f[i][j] f[i][j]与正确答案不符，我们试图寻找矛盾。我们分几种情况：
1、如果离其最近的 0 0 0在左上方（这里左上方包括正左方和正上方），但 f f f的与正确答案 u u u不同，设那个 0 0 0的坐标是 ( x , y ) (x,y) (x,y)，那么可以知道 A [ x : i , y : j ] A[x:i,y:j] A[x:i,y:j]这个矩形除了 A [ x ] [ y ] A[x][y] A[x][y]以外一定都是 1 1 1，在第一遍更新的时候， f [ x ] [ y ] = 0 f[x][y]=0 f[x][y]=0，接着由更新的方式知道， f [ x + 1 ] [ y ] ≤ 1 , ∀ k ≤ i − x , f [ x + k ] [ y ] ≤ k f[x+1][y]\le 1,\forall k\le i-x, f[x+k][y]\le k f[x+1][y]≤1,∀k≤i−x,f[x+k][y]≤k类似可知 ∀ l ≤ j − y , f [ i ] [ y + l ] ≤ i − x + l \forall l\le j - y, f[i][y+l]\le i-x+l ∀l≤j−y,f[i][y+l]≤i−x+l，所以 f [ i ] [ j ] ≤ i − x + j − y = u f[i][j]\le i-x+j-y=u f[i][j]≤i−x+j−y=u，所以 f [ i ] [ j ] ≤ u f[i][j]\le u f[i][j]≤u。如果 f [ i ] [ j ] < u f[i][j]<u f[i][j]<u，那一定存在一个矩形 A [ x : i , y : j ] A[x:i,y:j] A[x:i,y:j]内的非 ( i , j ) (i,j) (i,j)的坐标 ( a 1 , b 1 ) (a_1,b_1) (a1,b1)使得 f [ a 1 ] [ b 1 ] < u − ( i − a 1 ) − ( j − b 1 ) f[a_1][b_1]<u-(i-a_1)-(j-b_1) f[a1][b1]<u−(i−a1)−(j−b1)，考虑 ( a 1 , b 1 ) (a_1,b_1) (a1,b1)这个位置，离它最近的 0 0 0（之一）一定也是 A [ x ] [ y ] A[x][y] A[x][y]，否则就会导致与 A [ x ] [ y ] A[x][y] A[x][y]是离 A [ i ] [ j ] A[i][j] A[i][j]最近的 0 0 0这个结论矛盾。接下来是无穷递降法，由 ( a 1 , b 1 ) (a_1,b_1) (a1,b1)可以类似得到 ( a 2 , b 2 ) , ( a 3 , b 3 ) , . . . (a_2,b_2),(a_3,b_3),... (a2,b2),(a3,b3),...，一路推下去在有限步一定会推到 ( a k , b k ) = ( x , y ) (a_k,b_k)=(x,y) (ak,bk)=(x,y)，从而得到 f [ x ] [ y ] < 0 f[x][y]<0 f[x][y]<0，与 f [ x ] [ y ] = 0 f[x][y]=0 f[x][y]=0矛盾。所以得出，如果离 A [ i ] [ j ] A[i][j] A[i][j]最近的 0 0 0在其左上方，那么 f [ i ] [ j ] f[i][j] f[i][j]一定是正确答案。对于右下方同理；
2、如果离其最近的 0 0 0在左下方，设那个 0 0 0的坐标是 ( x , y ) (x,y) (x,y)，那么由于对于 f [ i ] [ j ] f[i][j] f[i][j]来说，这个 0 0 0是在左上方，而由上面的结论知道 f [ x ] [ j ] f[x][j] f[x][j]在第一轮遍历中已经存了正确答案了，那么在第二轮遍历中， f [ x ] [ j ] f[x][j] f[x][j]会用来去更新 f [ i ] [ j ] f[i][j] f[i][j]，所以 f [ i ] [ j ] f[i][j] f[i][j]存的也一定是正确答案。右上方同理。
综上， f f f最后存的一定是正确答案。
由证明知道，算法的关键是，第二遍遍历的时候，一定要直接对 f f f进行更新，而千万不能另外开一个数组 g g g，像第一遍遍历 A A A的时候去更新 g g g。主要问题是，如果离 A [ i ] [ j ] A[i][j] A[i][j]的 0 0 0（设坐标是 ( x , y ) (x,y) (x,y)）是在左下方， g [ x ] [ j ] g[x][j] g[x][j]里并不一定存储了正确答案！所以用 g [ x ] [ j ] g[x][j] g[x][j]去更新 g [ i ] [ j ] g[i][j] g[i][j]也是无法得到正确答案的。之后即使得到了 f f f和 g g g两个数组，最后也得不到最终的正确答案。
代码如下：
import java.util.Arrays;
public class Solution {
/**
* @param matrix: a 0-1 matrix
* @return: return a matrix
*/
public int[][] updateMatrix(int[][] matrix) {
// write your code here
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], m + n);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
dp[i][j] = 0;
} else {
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 = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] != 0) {
if (i < m - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}
if (j < n - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
}
}
}
return dp;
}
}
时间复杂度 O ( m n ) O(mn) O(mn)，空间 O ( 1 ) O(1) O(1)。
法2：BFS，思路可以参考https://blog.csdn.net/qq_46105170/article/details/106117602。代码方面，为了避免new出的对象占用空间太大，可以使用状态压缩的技巧。即，对于坐标 ( x , y ) (x,y) (x,y)，我们将 x ∗ n + y x*n+y x∗n+y这个整数入队，而对于一个整数，可以通过 ( k / n , k % n ) (k/n,k\%n) (k/n,k%n)的方式还原成坐标。代码如下：
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
/**
* @param matrix: a 0-1 matrix
* @return: return a matrix
*/
public int[][] updateMatrix(int[][] matrix) {
// write your code here
int m = matrix.length, n = matrix[0].length;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
queue.offer(i * n + j);
} else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int step = 0;
while (!queue.isEmpty()) {
step++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
// 还原成坐标
int x = cur / n, y = cur % n;
for (int j = 0; j < dirs.length; j++) {
int nextX = x + dirs[j][0], nextY = y + dirs[j][1];
if (inBound(nextX, nextY, matrix) && matrix[nextX][nextY] != 0) {
if (matrix[nextX][nextY] > step) {
matrix[nextX][nextY] = step;
queue.offer(nextX * n + nextY);
}
}
}
}
}
return matrix;
}
private boolean inBound(int x, int y, int[][] matrix) {
return 0 <= x && x < matrix.length && 0 <= y && y < matrix[0].length;
}
}
时空复杂度 O ( m n ) O(mn) O(mn)。
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)