add skeleton for 980

fishercoder1534 · fishercoder1534 · commit 5ace0fc141bf · 2020-02-18T16:14:30.000-08:00
diff --git a/README.md b/README.md
@@ -141,6 +141,7 @@ _If you like this project, please leave me a star._ &#9733;
 |987|[Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_987.java) | |Medium| Recursion
 |986|[Interval List Intersections](https://leetcode.com/problems/interval-list-intersections/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_986.java) | |Medium| Two Pointers
 |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) | |Easy| Array
+|980|[Unique Paths III](https://leetcode.com/problems/unique-paths-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_980.java) | |Hard| Backtracking, DFS
 |979|[Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_979.java) | |Medium| Recursion
 |977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_977.java) | |Easy| Array
 |976|[Largest Perimeter Triangle](https://leetcode.com/problems/largest-perimeter-triangle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_976.java) | |Easy| Math Array 
diff --git a/src/main/java/com/fishercoder/solutions/_980.java b/src/main/java/com/fishercoder/solutions/_980.java
@@ -0,0 +1,46 @@
+package com.fishercoder.solutions;
+
+/**
+ * 980. Unique Paths III
+ *
+ * On a 2-dimensional grid, there are 4 types of squares:
+ * 1 represents the starting square.  There is exactly one starting square.
+ * 2 represents the ending square.  There is exactly one ending square.
+ * 0 represents empty squares we can walk over.
+ * -1 represents obstacles that we cannot walk over.
+ * Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
+ *
+ * Example 1:
+ * Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
+ * Output: 2
+ * Explanation: We have the following two paths:
+ * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
+ * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
+ *
+ * Example 2:
+ * Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
+ * Output: 4
+ * Explanation: We have the following four paths:
+ * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
+ * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
+ * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
+ * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
+ *
+ * Example 3:
+ * Input: [[0,1],[2,0]]
+ * Output: 0
+ * Explanation:
+ * There is no path that walks over every empty square exactly once.
+ * Note that the starting and ending square can be anywhere in the grid.
+ *
+ * Note:
+ * 1 <= grid.length * grid[0].length <= 20
+ * */
+public class _980 {
+    public static class Solution1 {
+        public int uniquePathsIII(int[][] grid) {
+            //TODO: implement it
+            return -1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_980Test.java b/src/test/java/com/fishercoder/_980Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._980;
+import org.junit.BeforeClass;
+import org.junit.Ignore;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+@Ignore
+public class _980Test {
+    private static _980.Solution1 solution1;
+    private static int[][] grid;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _980.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        grid = new int[][]{
+                {1, 0, 0, 0},
+                {0, 0, 0, 0},
+                {0, 0, 2, -1},
+        };
+        assertEquals(2, solution1.uniquePathsIII(grid));
+    }
+
+}
