package com.fishercoder.solutions;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

 The distance between two adjacent cells is 1.
 Example 1:
 Input:

 0 0 0
 0 1 0
 0 0 0
 Output:
 0 0 0
 0 1 0
 0 0 0
 Example 2:
 Input:

 0 0 0
 0 1 0
 1 1 1
 Output:
 0 0 0
 0 1 0
 1 2 1

 Note:
 The number of elements of the given matrix will not exceed 10,000.
 There are at least one 0 in the given matrix.
 The cells are adjacent in only four directions: up, down, left and right.
 */
public class _542 {

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        int m = matrix.size();
        int n = matrix.get(0).size();
        Deque<int[]> deque = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix.get(i).get(j) == 0) {
                    deque.offer(new int[]{i, j});
                } else {
                    matrix.get(i).set(j, Integer.MAX_VALUE);
                }
            }
        }

        final int[] dirs = new int[]{0, 1, 0, -1, 0};
        while (!deque.isEmpty()) {
            int[] currentCell = deque.poll();
            for (int i = 0; i < dirs.length - 1; i++) {
                int nextRow = currentCell[0] + dirs[i];
                int nextCol = currentCell[1] + dirs[i + 1];
                if (nextRow < 0 || nextCol < 0 || nextRow >= m || nextCol >= n || matrix.get(nextRow).get(nextCol) <= matrix.get(currentCell[0]).get(currentCell[1]) + 1) {
                    continue;
                }
                deque.offer(new int[]{nextRow, nextCol});
                matrix.get(nextRow).set(nextCol, matrix.get(currentCell[0]).get(currentCell[1]) + 1);
            }
        }
        return matrix;
    }

}

@@ -110,16 +110,37 @@
 t;%0A%0A/**%0A
+ * 542. 01 Matrix%0A *%0A
  * Given
@@ -635,16 +635,57 @@
 _542 %7B%0A%0A
+    public static class Solution1 %7B%0A%0A    
     publ
@@ -754,24 +754,28 @@
 ) %7B%0A        
+    
 int m = matr
@@ -777,32 +777,36 @@
  matrix.size();%0A
+    
         int n = 
@@ -835,16 +835,20 @@
         
+    
 Deque%3Cin
@@ -880,32 +880,36 @@
 st%3C%3E();%0A        
+    
 for (int i = 0; 
@@ -926,32 +926,36 @@
 ) %7B%0A            
+  
+  
 for (int j = 0; 
@@ -964,24 +964,28 @@
 %3C n; j++) %7B%0A
+    
             
@@ -1017,24 +1017,28 @@
 (j) == 0) %7B%0A
+    
             
@@ -1091,16 +1091,20 @@
         
+    
 %7D else %7B
@@ -1104,16 +1104,20 @@
  else %7B%0A
+    
         
@@ -1177,34 +1177,42 @@
                 
+ 
-%7D%0A
+   %7D%0A    
             %7D%0A  
@@ -1217,19 +1217,27 @@
         
+   
+ 
 %7D%0A%0A
+    
         
@@ -1290,16 +1290,20 @@
         
+    
 while (!
@@ -1333,16 +1333,20 @@
         
+ 
+   
 int%5B%5D cu
@@ -1367,24 +1367,28 @@
 que.poll();%0A
+    
             
@@ -1439,32 +1439,36 @@
                 
+   
+ 
 int nextRow = cu
@@ -1491,16 +1491,20 @@
 irs%5Bi%5D;%0A
+    
         
@@ -1555,16 +1555,20 @@
 i + 1%5D;%0A
+    
         
@@ -1751,16 +1751,20 @@
         
+    
 continue
@@ -1773,34 +1773,40 @@
                 
-%7D%0A
+    %7D%0A  
                 
@@ -1797,32 +1797,34 @@
                 
+  
 deque.offer(new 
@@ -1845,24 +1845,28 @@
  nextCol%7D);%0A
+    
             
@@ -1959,34 +1959,42 @@
 1);%0A            
+   
+ 
 %7D%0A
+    
         %7D%0A      
@@ -1979,32 +1979,36 @@
 %7D%0A            %7D%0A
+    
         return m
@@ -2014,16 +2014,26 @@
 matrix;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 542