[数据结构与算法]经典动态规划：二维（02）

题目：

给定一个由 0 和 1 组成的矩阵 mat?，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1?

题解：

对于矩阵中的任意一个 1 以及一个 0，我们如何从这个 1 到达 0 并且距离最短呢？根据上面的做法，我们可以从 1 开始，先在水平方向移动，直到与 0 在同一列，随后再在竖直方向上移动，直到到达 0 的位置。这样一来，从一个固定的 1 走到任意一个 0，在距离最短的前提下可能有四种方法：

只有 水平向左移动 和 竖直向上移动；

只有 水平向左移动 和 竖直向下移动；

只有 水平向右移动 和 竖直向上移动；

只有 水平向右移动 和 竖直向下移动。

然后根据这四种情况作出四种方向的循环：

class Solution {
    static int [][]dir={{-1,0},{1,0},{0,-1},{0,1}};
    public int[][] updateMatrix(int[][] mat) {
      int m=mat.length,n=mat[0].length;//如果合理-1，那么下面的for循环那里就要<=
       // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
       int[][]dist=new int[m][n];
       for(int i=0;i<m;i++){
           Arrays.fill(dist[i],Integer.MAX_VALUE/2);
       }

 // 如果 (i, j) 的元素为 0，那么距离为 0
 for(int i=0;i<m;i++){//上面没有——1，这里就是<
     for(int j=0;j<n;j++){
         if(mat[i][j]==0){
             dist[i][j]=0;
         }
     }
 }

 // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
 for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
    if(i-1>=0){
        dist[i][j]=Math.min(dist[i][j],dist[i-1][j]+1);
    }
    if(j-1>=0){
        dist[i][j]=Math.min(dist[i][j],dist[i][j-1]+1);
    }
    }
 }

     // 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
     for(int i=m-1;i>=0;--i){
         for(int j=0;j<n;++j){
             if(i+1<m){
                 dist[i][j]=Math.min(dist[i][j],dist[i+1][j]+1);
             }
             if(j-1>=0){
                 dist[i][j]=Math.min(dist[i][j],dist[i][j-1]+1);
             }
         }
     }

 // 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
 for(int i=0;i<m;++i){
     for(int j=n-1;j>=0;--j){
         if(i-1>=0){
             dist[i][j]=Math.min(dist[i][j],dist[i-1][j]+1);
         }
         if(j+1<n){
             dist[i][j]=Math.min(dist[i][j],dist[i][j+1]+1);
         }
     }
 }

// 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
for(int i=m-1;i>=0;--i){
    for(int j=n-1;j>=0;--j){
        if(i+1<m){
            dist[i][j]=Math.min(dist[i][j],dist[i+1][j]+1);
        }
        if(j+1<n){
            dist[i][j]=Math.min(dist[i][j],dist[i][j+1]+1);
        }
    }
}

return dist;



    }
}

题目来自力扣542题.