leetcode542 01矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

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

示例 1:
输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0
示例 2:
输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1
注意:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思路：可以动态规划，因为不可能出现：

拐过来形成最优解。所以正着扫一遍算两个方向。反着扫一遍算两个方向即可。

dp[i][j]代表这个位置的最优解。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public int[][] updateMatrix(int[][] matrix) {
     
    
   

    

     

    
    

     
 int l1 = matrix.length;
     
    
   

    

     

    
    

     
 int l2 = matrix[0].length;
     
    
   

    

     

    
    

     
 if(l1 == 0) return matrix;
     
    
   

    

     

    
    

     
 int[][] r = new int[l1][l2];
     
    
   

    

     

    
    

     
 for(int i = 0; i < l1; ++i) {
     
    
   

    

     

    
    

     
 for(int j = 0; j < l2; ++j) {
     
    
   

    

     

    
    

     

       r[i][j] = 205;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = 0; i < l1; ++i) {
     
    
   

    

     

    
    

     
 for(int j = 0; j < l2; ++j) {
     
    
   

    

     

    
    

     
 if(matrix[i][j] == 0)
     
    
   

    

     

    
    

     

       r[i][j] = 0;
     
    
   

    

     

    
    

     
 else {
     
    
   

    

     

    
    

     
 if(i > 0)
     
    
   

    

     

    
    

     

       r[i][j] = Math.min(r[i][j],r[i-1][j] + 1);
     
    
   

    

     

    
    

     
 if(j > 0)
     
    
   

    

     

    
    

     

       r[i][j] = Math.min(r[i][j],r[i][j-1] + 1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = l1-1; i >= 0; --i) {
     
    
   

    

     

    
    

     
 for(int j = l2-1; j >= 0; --j) {
     
    
   

    

     

    
    

     
 if(matrix[i][j] == 0)
     
    
   

    

     

    
    

     

       r[i][j] = 0;
     
    
   

    

     

    
    

     
 else {
     
    
   

    

     

    
    

     
 if(i < l1-1)
     
    
   

    

     

    
    

     

       r[i][j] = Math.min(r[i][j],r[i+1][j] + 1);
     
    
   

    

     

    
    

     
 if(j < l2-1)
     
    
   

    

     

    
    

     

       r[i][j] = Math.min(r[i][j],r[i][j+1] + 1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return r;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103252643