add 1091

fishercoder1534 · fishercoder1534 · commit f0e6e94ca76e · 2021-02-13T09:27:17.000-08:00
diff --git a/README.md b/README.md
@@ -289,6 +289,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1100|[Find K-Length Substrings With No Repeated Characters](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1100.java) | |Medium|String, Sliding Window|
 |1099|[Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1099.java) |  [:tv:](https://www.youtube.com/watch?v=2Uq7p7HE0TI)|Easy||
 |1090|[Largest Values From Labels](https://leetcode.com/problems/largest-values-from-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1090.java) | [:tv:](https://youtu.be/E0OkE3G95vU)|Medium|HashTable, Greedy|
+|1091|[Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1091.java) | |Medium|BFS|
 |1089|[Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1089.java) | |Easy||
 |1087|[Brace Expansion](https://leetcode.com/problems/brace-expansion/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1087.java) | |Medium|Backtracking|
 |1086|[High Five](https://leetcode.com/problems/high-five/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1086.java) | [:tv:](https://www.youtube.com/watch?v=3iqC5J4l0Cc)|Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1091.java b/src/main/java/com/fishercoder/solutions/_1091.java
@@ -0,0 +1,42 @@
+package com.fishercoder.solutions;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+public class _1091 {
+    public static class Solution1 {
+        int[] directions = new int[]{0, 1, 1, 0, -1, 1, -1, -1, 0};
+
+        public int shortestPathBinaryMatrix(int[][] grid) {
+            int m = grid.length;
+            int n = grid[0].length;
+            if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
+                return -1;
+            }
+            int minPath = 0;
+            Queue<int[]> queue = new LinkedList<>();
+            queue.offer(new int[]{0, 0});
+            boolean[][] visited = new boolean[m][n];
+            visited[0][0] = true;
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                for (int i = 0; i < size; i++) {
+                    int[] curr = queue.poll();
+                    if (curr[0] == m - 1 && curr[1] == n - 1) {
+                        return minPath + 1;
+                    }
+                    for (int j = 0; j < directions.length - 1; j++) {
+                        int newx = directions[j] + curr[0];
+                        int newy = directions[j + 1] + curr[1];
+                        if (newx >= 0 && newx < n && newy >= 0 && newy < n && !visited[newx][newy] && grid[newx][newy] == 0) {
+                            queue.offer(new int[]{newx, newy});
+                            visited[newx][newy] = true;
+                        }
+                    }
+                }
+                minPath++;
+            }
+            return -1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1091Test.java b/src/test/java/com/fishercoder/_1091Test.java
@@ -0,0 +1,56 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._1091;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1091Test {
+    private static _1091.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1091.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(2, solution1.shortestPathBinaryMatrix(new int[][]{
+                {0, 1},
+                {1, 0}
+        }));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(4, solution1.shortestPathBinaryMatrix(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,0,0],[1,1,0],[1,1,0]")));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(-1, solution1.shortestPathBinaryMatrix(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,0,0],[1,1,0],[1,1,0]")));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(-1, solution1.shortestPathBinaryMatrix(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,0,0],[1,1,0],[1,1,1]")));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals(1, solution1.shortestPathBinaryMatrix(new int[][]{
+                {0}
+        }));
+    }
+
+    @Test
+    public void test6() {
+        assertEquals(7, solution1.shortestPathBinaryMatrix(new int[][]{
+                {0, 1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1, 0}
+        }))
+        ;
+    }
+
+}
