package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode.com/problems/rotting-oranges/
 */
public class Problem994 {
    public int orangesRotting(int[][] grid) {
        int maxRow = grid.length;
        int maxCol = maxRow > 0 ? grid[0].length : 0;
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    int val = bfs(grid, maxRow, maxCol, i, j);
                    if (val > 0) {
                        answer = Math.min(answer, val);
                    }
                }
            }
        }
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }

    private static int bfs(int[][] grid, int maxRow, int maxCol, int row, int col) {
        int count = -1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{row, col});
        while (!queue.isEmpty()) {
            Queue<int[]> tmp = new LinkedList<>();
            count++;
            while (!queue.isEmpty()) {
                int[] current = queue.remove();
                row = current[0];
                col = current[1];
                if (row - 1 >= 0 && grid[row - 1][col] == 1) {
                    grid[row - 1][col] = 2;
                    tmp.add(new int[]{row - 1, col});
                }
                if (col + 1 < maxCol && grid[row][col + 1] == 1) {
                    grid[row][col + 1] = 2;
                    tmp.add(new int[]{row, col + 1});
                }
                if (row + 1 < maxRow && grid[row + 1][col] == 1) {
                    grid[row + 1][col] = 2;
                    tmp.add(new int[]{row + 1, col});
                }
                if (col - 1 >= 0 && grid[row][col - 1] == 1) {
                    grid[row][col - 1] = 2;
                    tmp.add(new int[]{row, col - 1});
                }
            }
            queue.addAll(tmp);
        }
        return count;
    }

    public static void main(String[] args) {
        Problem994 prob = new Problem994();
//        System.out.println(prob.orangesRotting(new int[][]{
//            {2, 1, 1},
//            {1, 1, 0},
//            {0, 1, 1}
//        })); // 4
//        System.out.println(prob.orangesRotting(new int[][]{
//            {2, 1, 1},
//            {0, 1, 1},
//            {1, 0, 1}
//        })); // -1
//        System.out.println(prob.orangesRotting(new int[][]{
//            {0, 2}
//        })); // 0
//        System.out.println(prob.orangesRotting(new int[][]{
//            {1, 0, 1}
//        })); // -1
//        System.out.println(prob.orangesRotting(new int[][]{
//            {0, 1}
//        })); // -1
//        System.out.println(prob.orangesRotting(new int[][]{
//            {0}
//        })); // 0
//        System.out.println(prob.orangesRotting(new int[][]{
//            {2, 2, 2, 1, 1}
//        })); // 2
        System.out.println(prob.orangesRotting(new int[][]{
            {2, 2},
            {1, 1},
            {0, 0},
            {2, 0}
        })); // 1
    }
}

@@ -296,38 +296,78 @@
     
-int answer = Integer.MAX_VALUE
+Queue%3Cint%5B%5D%3E queue = new LinkedList%3C%3E();%0A        boolean fresh = false
 ;%0A  
@@ -530,295 +530,35 @@
     
-int val = bfs(grid, maxRow, maxCol, i, j);%0A                    if (val %3E 0) %7B%0A                        answer = Math.min(answer, val);%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        for (int i = 0; i %3C maxRow; i++) %7B%0A            for (int j = 0; j %3C maxCol; j++) %7B
+queue.add(new int%5B%5D%7Bi, j%7D);
 %0A   
@@ -562,32 +562,39 @@
                 
+%7D else 
 if (grid%5Bi%5D%5Bj%5D =
@@ -624,17 +624,20 @@
     
+f
 re
-turn -1
+sh = true
 ;%0A  
@@ -688,260 +688,96 @@
     
-return answer == Integer.MAX_VALUE ? 0 : answer;%0A    %7D%0A%0A    private static int bfs(int%5B%5D%5B%5D grid, int maxRow, int maxCol, int row, int col) %7B%0A        int count = -1;%0A        Queue%3Cint%5B%5D%3E queue = new LinkedList%3C%3E();%0A        queue.add(new int%5B%5D%7Brow, col%7D)
+if (queue.isEmpty() && !fresh) %7B%0A            return 0;%0A        %7D%0A        int answer = -1
 ;%0A  
@@ -872,21 +872,22 @@
         
-count
+answer
 ++;%0A    
@@ -985,16 +985,20 @@
         
+int 
 row = cu
@@ -1023,16 +1023,20 @@
         
+int 
 col = cu
@@ -1836,939 +1836,192 @@
     
-return count;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem994 prob = new Problem994();%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B2, 1, 1%7D,%0A//            %7B1, 1, 0%7D,%0A//            %7B0, 1, 1%7D%0A//        %7D)); // 4%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B2, 1, 1%7D,%0A//            %7B0, 1, 1%7D,%0A//            %7B1, 0, 1%7D%0A//        %7D)); // -1%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B0, 2%7D%0A//        %7D)); // 0%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B1, 0, 1%7D%0A//        %7D)); // -1%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B0, 1%7D%0A//        %7D)); // -1%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B0%7D%0A//        %7D)); // 0%0A//        System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A//            %7B2, 2, 2, 1, 1%7D%0A//
+for (int i = 0; i %3C maxRow; i++) %7B%0A            for (int j = 0; j %3C maxCol; j++) %7B%0A                if (grid%5Bi%5D%5Bj%5D == 1) %7B%0A                    return -1;%0A                %7D%0A            %7D%0A
     
@@ -2029,16 +2029,8 @@
    %7D
-)); // 2
 %0A   
@@ -2038,156 +2038,22 @@
     
-System.out.println(prob.orangesRotting(new int%5B%5D%5B%5D%7B%0A            %7B2, 2%7D,%0A            %7B1, 1%7D,%0A            %7B0, 0%7D,%0A            %7B2, 0%7D%0A        %7D)); // 1
+return answer;
 %0A   

Solve problem 994