DFS_BFS之钥匙和房间[Grampus]
方法1:BFS
- 利用
set记录被访问的房间的个数，如果刚好等于所有被访问的房间，为true，否则为false - 当房间被访问过，就不再添加房间进
set，初始化时，将0号房间加入到set中
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> set = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
int n = rooms.size();
List<Integer> zeroRoom = rooms.get(0);
set.add(0);
for (int i : zeroRoom) {
queue.offer(i);
set.add(i);
}
while (!queue.isEmpty()) {
int curr = queue.poll();
List<Integer> currRoom = rooms.get(curr);
for (int c : currRoom) {
if (!set.contains(c)) {
queue.offer(c);
set.add(c);
}
}
}
return set.size() == n;
}
另外一种写法：
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Queue<Integer> queue = new LinkedList<>();
int n = rooms.size();
boolean[] visited = new boolean[n];
List<Integer> zeroRoom = rooms.get(0);
visited[0] = true;
for (int i : zeroRoom) queue.offer(i);
while (!queue.isEmpty()) {
int curr = queue.poll();
visited[curr] = true;
List<Integer> currRoom = rooms.get(curr);
for (int c : currRoom) {
if (!visited[c]) {
queue.offer(c);
visited[c] = true;
}
}
}
for (boolean b : visited) if (!b) return false;
return true;
}
方法2:DFS
dfs的三个参数：rooms房间，idx当前房间的索引号，visited被访问的房间列表- 出口条件：当该房间被访问，返回
- 计算：房间都被访问，返回
true,有一个房间未被访问，返回false
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] visited = new boolean[n];
dfs(rooms, 0, visited);
for (boolean b : visited) if (!b) return false;
return true;
}
private void dfs(List<List<Integer>> rooms, int idx, boolean[] visited) {
if (visited[idx]) return;
visited[idx] = true;
for (int i : rooms.get(idx)) dfs(rooms, i, visited);
}
文档信息
- 本文作者：wat1r
- 本文链接：https://wat1r.github.io/2020/08/31/keys-and-room/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）