add 841

fishercoder1534 · fishercoder1534 · commit 95bae3c2d792 · 2020-02-14T15:44:29.000-08:00
diff --git a/README.md b/README.md
@@ -179,6 +179,7 @@ _If you like this project, please leave me a star._ &#9733;
 |852|[Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_852.java) |  |Easy|
 |849|[Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_849.java) | |Easy|
 |844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_844.java) | |Easy|
+|841|[Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_841.java) |  |Easy|DFS, Graph
 |840|[Magic Squares In Grid](https://leetcode.com/problems/magic-squares-in-grid/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_840.java) |  |Easy|
 |836|[Rectangle Overlap](https://leetcode.com/problems/rectangle-overlap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_836.java) | [:tv:](https://youtu.be/o6hHUk4DOW0) |Easy|
 |832|[Flipping an Image](https://leetcode.com/problems/flipping-an-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_832.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_841.java b/src/main/java/com/fishercoder/solutions/_841.java
@@ -0,0 +1,67 @@
+package com.fishercoder.solutions;
+
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+
+/**
+ * 841. Keys and Rooms
+ *
+ * There are N rooms and you start in room 0.
+ * Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
+ * Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.
+ * A key rooms[i][j] = v opens the room with number v.
+ * Initially, all the rooms start locked (except for room 0).
+ * You can walk back and forth between rooms freely.
+ * Return true if and only if you can enter every room.
+ *
+ * Example 1:
+ * Input: [[1],[2],[3],[]]
+ * Output: true
+ * Explanation:
+ * We start in room 0, and pick up key 1.
+ * We then go to room 1, and pick up key 2.
+ * We then go to room 2, and pick up key 3.
+ * We then go to room 3.  Since we were able to go to every room, we return true.
+ *
+ * Example 2:
+ * Input: [[1,3],[3,0,1],[2],[0]]
+ * Output: false
+ * Explanation: We can't enter the room with number 2.
+ *
+ * Note:
+ * 1 <= rooms.length <= 1000
+ * 0 <= rooms[i].length <= 1000
+ * The number of keys in all rooms combined is at most 3000.
+ * */
+public class _841 {
+    public static class Solution1 {
+        public boolean canVisitAllRooms(List<List<Integer>> rooms) {
+            Set<Integer> unvisitedRooms = new HashSet<>();
+            for (int i = 1; i < rooms.size(); i++) {
+                unvisitedRooms.add(i);
+            }
+            List<Integer> keys = rooms.get(0);
+            Queue<Integer> queue = new LinkedList<>();
+            for (int key : keys) {
+                queue.offer(key);
+            }
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                for (int i = 0; i < size; i++) {
+                    int roomIndex = queue.poll();
+                    unvisitedRooms.remove(roomIndex);
+                    for (int j = 0; j < rooms.get(roomIndex).size(); j++) {
+                        Integer nextRoom = rooms.get(roomIndex).get(j);
+                        if (unvisitedRooms.contains(nextRoom) && !queue.contains(nextRoom)) {
+                            queue.offer(nextRoom);
+                        }
+                    }
+                }
+            }
+            return unvisitedRooms.isEmpty();
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_841Test.java b/src/test/java/com/fishercoder/_841Test.java
@@ -0,0 +1,41 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._841;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+
+public class _841Test {
+    private static _841.Solution1 solution1;
+    private static List<List<Integer>> rooms;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _841.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        rooms = new ArrayList<>();
+        rooms.add(Arrays.asList(1));
+        rooms.add(Arrays.asList(2));
+        rooms.add(Arrays.asList(3));
+        rooms.add(Arrays.asList());
+        assertEquals(true, solution1.canVisitAllRooms(rooms));
+    }
+
+    @Test
+    public void test2() {
+        rooms = new ArrayList<>();
+        rooms.add(Arrays.asList(1, 3));
+        rooms.add(Arrays.asList(3, 0, 1));
+        rooms.add(Arrays.asList(2));
+        rooms.add(Arrays.asList(0));
+        assertEquals(false, solution1.canVisitAllRooms(rooms));
+    }
+}
