add solution for 980

fishercoder1534 · fishercoder1534 · commit 2ff17c094fe1 · 2020-02-18T17:08:41.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_980.java b/src/main/java/com/fishercoder/solutions/_980.java
@@ -38,9 +38,60 @@
  * */
 public class _980 {
     public static class Solution1 {
+
+        int[] directions = new int[]{0, 1, 0, -1, 0};
+        int paths = 0;
+
         public int uniquePathsIII(int[][] grid) {
-            //TODO: implement it
-            return -1;
+            int[] start = findStart(grid);
+            int m = grid.length;
+            int n = grid[0].length;
+            boolean[][] visited = new boolean[m][n];
+            visited[start[0]][start[1]] = true;
+            return backtracking(grid, m, n, visited, start);
+        }
+
+        private int backtracking(int[][] grid, int m, int n, boolean[][] visited, int[] start) {
+            for (int i = 0; i < directions.length - 1; i++) {
+                int nextX = directions[i] + start[0];
+                int nextY = directions[i + 1] + start[1];
+                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] != -1 && !visited[nextX][nextY]) {
+                    if (grid[nextX][nextY] == 2) {
+                        if (allZeroesVisited(visited, grid)) {
+                            paths++;
+                            return paths;
+                        } else {
+                            continue;
+                        }
+                    }
+                    visited[nextX][nextY] = true;
+                    backtracking(grid, m, n, visited, new int[]{nextX, nextY});
+                    visited[nextX][nextY] = false;
+                }
+            }
+            return paths;
+        }
+
+        private boolean allZeroesVisited(boolean[][] visited, int[][] grid) {
+            for (int i = 0; i < grid.length; i++) {
+                for (int j = 0; j < grid[0].length; j++) {
+                    if (grid[i][j] == 0 && !visited[i][j]) {
+                        return false;
+                    }
+                }
+            }
+            return true;
+        }
+
+        private int[] findStart(int[][] grid) {
+            for (int i = 0; i < grid.length; i++) {
+                for (int j = 0; j < grid[0].length; j++) {
+                    if (grid[i][j] == 1) {
+                        return new int[]{i, j};
+                    }
+                }
+            }
+            return null;
         }
     }
 }
diff --git a/src/test/java/com/fishercoder/_980Test.java b/src/test/java/com/fishercoder/_980Test.java
@@ -1,24 +1,17 @@
 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() {
+        solution1 = new _980.Solution1();
         grid = new int[][]{
                 {1, 0, 0, 0},
                 {0, 0, 0, 0},
@@ -27,4 +20,25 @@ public void test1() {
         assertEquals(2, solution1.uniquePathsIII(grid));
     }
 
+    @Test
+    public void test2() {
+        solution1 = new _980.Solution1();
+        grid = new int[][]{
+                {1, 0, 0, 0},
+                {0, 0, 0, 0},
+                {0, 0, 0, 2},
+        };
+        assertEquals(4, solution1.uniquePathsIII(grid));
+    }
+
+    @Test
+    public void test3() {
+        solution1 = new _980.Solution1();
+        grid = new int[][]{
+                {0, 1},
+                {2, 0},
+        };
+        assertEquals(0, solution1.uniquePathsIII(grid));
+    }
+
 }
