add 994

fishercoder1534 · fishercoder1534 · commit d3c2da2d11b8 · 2019-02-19T08:06:32.000-08:00
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|994|[Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_994.java) | O(m*2*n*2) | O(m*n) | |Easy| BFS
 |993|[Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_993.java) | O(n) | O(m) (m is length of the nodes that has the max number of nodes on the same level) | |Easy| Tree, BFS
 |989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | O(max(N, logk)) | O(max(N, logk)) | |Easy| Array
 |985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | O(n) | O(n) | |Easy| Array
diff --git a/src/main/java/com/fishercoder/solutions/_994.java b/src/main/java/com/fishercoder/solutions/_994.java
@@ -0,0 +1,84 @@
+package com.fishercoder.solutions;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * 994. Rotting Oranges
+ *
+ * In a given grid, each cell can have one of three values:
+ *
+ * the value 0 representing an empty cell;
+ * the value 1 representing a fresh orange;
+ * the value 2 representing a rotten orange.
+ *
+ * Every minute, any fresh orange that is adjacent (4-directionally) to a
+ * rotten orange becomes rotten.
+ *
+ * Return the minimum number of minutes that must elapse until no cell has a fresh orange.
+ * If this is impossible, return -1 instead.
+ *
+ * Example 1:
+ * Input: [[2,1,1],[1,1,0],[0,1,1]]
+ * Output: 4
+ *
+ * Example 2:
+ * Input: [[2,1,1],[0,1,1],[1,0,1]]
+ * Output: -1
+ * Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
+ *
+ * Example 3:
+ * Input: [[0,2]]
+ * Output: 0
+ * Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.
+ *
+ * Note:
+ *
+ * 1 <= grid.length <= 10
+ * 1 <= grid[0].length <= 10
+ * grid[i][j] is only 0, 1, or 2.
+ */
+public class _994 {
+  public static class Solution1 {
+    int[] directions = new int[] {0, 1, 0, -1, 0};
+
+    public int orangesRotting(int[][] grid) {
+      Queue<int[]> rottens = new LinkedList<>();
+      for (int i = 0; i < grid.length; i++) {
+        for (int j = 0; j < grid[0].length; j++) {
+          if (grid[i][j] == 2) {
+            rottens.add(new int[] {i, j});
+          }
+        }
+      }
+      int times = 0;
+      while (!rottens.isEmpty()) {
+        int size = rottens.size();
+        boolean counted = false;
+        for (int k = 0; k < size; k++) {
+          int[] rotten = rottens.poll();
+          for (int i = 0; i < 4; i++) {
+            int x = rotten[0] + directions[i];
+            int y = rotten[1] + directions[i + 1];
+            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
+              grid[x][y] = 2;
+              if (!counted) {
+                times++;
+              }
+              counted = true;
+              rottens.add(new int[] {x, y});
+            }
+          }
+        }
+      }
+      for (int i = 0; i < grid.length; i++) {
+        for (int j = 0; j < grid[0].length; j++) {
+          if (grid[i][j] == 1) {
+            return -1;
+          }
+        }
+      }
+      return times;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_994Test.java b/src/test/java/com/fishercoder/_994Test.java
@@ -0,0 +1,45 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._994;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _994Test {
+  private static _994.Solution1 solution1;
+  private static int[][] grid;
+
+  @BeforeClass
+  public static void setUp() {
+    solution1 = new _994.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    grid = new int[][] {
+        {2, 1, 1},
+        {1, 1, 0},
+        {0, 1, 1}
+    };
+    assertEquals(4, solution1.orangesRotting(grid));
+  }
+
+  @Test
+  public void test2() {
+    grid = new int[][] {
+        {2, 1, 1},
+        {0, 1, 1},
+        {1, 0, 1}
+    };
+    assertEquals(-1, solution1.orangesRotting(grid));
+  }
+
+  @Test
+  public void test3() {
+    grid = new int[][] {
+        {0, 2}
+    };
+    assertEquals(0, solution1.orangesRotting(grid));
+  }
+}
