package com.fishercoder.solutions;

/**
 * 749. Contain Virus
 *
 * A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.
 * The world is modeled as a 2-D array of cells, where 0 represents uninfected cells,
 * and 1 represents cells contaminated with the virus.
 * A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.
 * Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall.
 * Resources are limited. Each day, you can install walls around only one region --
 * the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.
 * Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

 Example 1:
 Input: grid =
 [[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]

 Output: 10
 Explanation:
 There are 2 contaminated regions.
 On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

 [[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

 On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.


 Example 2:
 Input: grid =
 [[1,1,1],
 [1,0,1],
 [1,1,1]]

 Output: 4
 Explanation: Even though there is only one cell saved, there are 4 walls built.
 Notice that walls are only built on the shared boundary of two different cells.


 Example 3:
 Input: grid =
 [[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
 Output: 13
 Explanation: The region on the left only builds two new walls.
 Note:
 The number of rows and columns of grid will each be in the range [1, 50].
 Each grid[i][j] will be either 0 or 1.
 Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.
 */
public class _749 {
  public static class Solution1 {
    public int containVirus(int[][] grid) {
      return -1;
    }
  }
}

@@ -33,2098 +33,95 @@
 s;%0A%0A
-/**%0A * 749. Contain Virus%0A *%0A * A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.%0A * The world is modeled as a 2-D array of cells, where 0 represents uninfected cells,%0A * and 1 represents cells contaminated with the virus.%0A * A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.%0A * Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall.%0A * Resources are limited. Each day, you can install walls around only one region --%0A * the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.%0A * Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.%0A%0A Example 1:%0A Input: grid =%0A %5B%5B0,1,0,0,0,0,0,1%5D,%0A %5B0,1,0,0,0,0,0,1%5D,%0A %5B0,0,0,0,0,0,0,1%5D,%0A %5B0,0,0,0,0,0,0,0%5D%5D%0A%0A Output: 10%0A Explanation:%0A There are 2 contaminated regions.%0A On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:%0A%0A %5B%5B0,1,0,0,0,0,1,1%5D,%0A %5B0,1,0,0,0,0,1,1%5D,%0A %5B0,0,0,0,0,0,1,1%5D,%0A %5B0,0,0,0,0,0,0,1%5D%5D%0A%0A On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.%0A%0A%0A Example 2:%0A Input: grid =%0A %5B%5B1,1,1%5D,%0A %5B1,0,1%5D,%0A %5B1,1,1%5D%5D%0A%0A Output: 4%0A Explanation: Even though there is only one cell saved, there are 4 walls built.%0A Notice that walls are only built on the shared boundary of two different cells.%0A%0A%0A Example 3:%0A Input: grid =%0A %5B%5B1,1,1,0,0,0,0,0,0%5D,%0A %5B1,0,1,0,1,1,1,1,1%5D,%0A %5B1,1,1,0,0,0,0,0,0%5D%5D%0A Output: 13%0A Explanation: The region on the left only builds two new walls.%0A Note:%0A The number of rows and columns of grid will each be in the range %5B1, 50%5D.%0A Each grid%5Bi%5D%5Bj%5D will be either 0 or 1.%0A Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.%0A */%0Apublic class _749 %7B%0A  public static class Solution1 %7B%0A
+public class _749 %7B%0A    public static class Solution1 %7B%0A      //TODO: implement it%0A    
     
@@ -160,16 +160,22 @@
 grid) %7B%0A
+      
       re
@@ -187,16 +187,22 @@
 -1;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 749