今天挑一个广搜的题目做一下。
其实我广搜的题熟练度一般/(ㄒoㄒ)/~~ 主要还是太久没做了……
这个题目不是很难，非常适合寻找手感……
这里先贴上别的大佬整理的知识点讲解：
BFS是有套路可言的：
void bfs(起始点) {
将起始点放入队列中;
标记起点访问;
while (如果队列不为空) { // 一般采用while ，当然也可以使用递归
访问队列中队首元素x;
删除队首元素;
for (x 所有相邻点) {
if (该点未被访问过且合法) {
将该点加入队列末尾;
if (该结点是目标状态) { // 达到目标，提前结束终止循环
置 flag= true;
break;
}
}
}
}
队列为空，广搜结束;
}对于这道题目，上面模板完全够用。不过我有点毛手毛脚，每一次提交都会发现自己还有一些特殊情况没有考虑。所以大概提交了三次，才完全覆盖所有的情况。
具体因为什么原因WA的，记不太起来了……但有一些大概的印象。大概有以下几个方面：
1、判断是否访问过每一个房间的标准有误。我记得我是通过创建visited的List集合解决的。但集合这种数据结构有一个问题：不能查重，我是通过判断visited的长度与rooms的长度是否相等
visited.size() == rooms.size()
来得出是否遍历完的结果。所以这个长度是很关键的，没有查重时，有重复的元素时就会得出错误的长度。因此，最终我换成了Set。
2、入口结点的元素没有加到邻接点集合中。我用neighborPoints来存每个结点的邻接点。但是没有把入口位置也就是0号结点的内容存进去……最后也会导致结果出错。
3、没有判断首元素（0号房间）内容为空的情况。即，0号房间中没有钥匙的情况。一上来就调用0号元素值，直接异常了。
4、在线OJ不能使用static变量。从本地拷贝过去的时候没改（因为牛客上似乎可以），结果代码一样，在线OJ结果和本地不一样。还好我疑惑的时间不是很长……
5、巩固了一些方法：
集合的addAll()方法非常方便；
neighborPoints.addAll(rooms.get(0));
neighborPoints.addAll(rooms.get(cur)); //获得cur房间的所有钥匙
Map的getOrDefault()方法也很方便，久了没用容易想不起：
status.getOrDefault(neighbor, false)
最终AC的代码如下：
class Solution {
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
Map<Integer, Boolean> status = new HashMap<Integer, Boolean>();
List<Integer> neighborPoints = new ArrayList<>();
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
System.out.println(rooms);
if(rooms.get(0).isEmpty()){
return false;
}
int first = rooms.get(0).get(0); //将起点放入队列
neighborPoints.addAll(rooms.get(0));
visited.add(0);
queue.add(first);
status.put(first, false);
while(!queue.isEmpty()) {
int cur = queue.poll();
status.put(cur, true);
// System.out.println(cur);
visited.add(cur);
neighborPoints.addAll(rooms.get(cur)); //获得cur房间的所有钥匙
for (Integer neighbor : neighborPoints) {
if(!status.getOrDefault(neighbor, false)) // 未遍历
{
if(queue.contains(neighbor)) {
continue;
}
queue.add(neighbor);
status.put(neighbor, false);
}
}
}
return visited.size() == rooms.size();
}
}本地的测试代码：
import java.util.*;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 12569
* Date: 2023-06-05
* Time: 9:35
*/
public class Test2 {
Deque<Integer> queue = new ArrayDeque<>();
static Set<Integer> visited = new HashSet<>();
Map<Integer, Boolean> status = new HashMap<Integer, Boolean>();
List<Integer> neighborPoints = new ArrayList<>();
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
System.out.println(rooms);
int first = rooms.get(0).get(0); //将起点放入队列
neighborPoints.addAll(rooms.get(0));
visited.add(0);
queue.add(first);
status.put(first, false);
while(!queue.isEmpty()) {
int cur = queue.poll();
status.put(cur, true);
// System.out.println(cur);
visited.add(cur);
neighborPoints.addAll(rooms.get(cur)); //获得cur房间的所有钥匙
for (Integer neighbor : neighborPoints) {
if(!status.getOrDefault(neighbor, false)) // 未遍历
{
if(queue.contains(neighbor)) {
continue;
}
queue.add(neighbor);
status.put(neighbor, false);
}
}
}
return visited.size() == rooms.size();
}
public static void main(String[] args) {
// [2,3],[],[2],[1,3]
Test2 test2 = new Test2();
List<Integer> r0 = new ArrayList<Integer>();
r0.add(1);
// r0.add(2);
r0.add(3);
List<Integer> r1 = new ArrayList<Integer>();
r1.add(3);
r1.add(0);
r1.add(1);
// r1.add(2);
List<Integer> r2 = new ArrayList<Integer>();
r2.add(2);
List<Integer> r3 = new ArrayList<Integer>();
// r3.add(1);
// r3.add(3);
r3.add(0);
List<List<Integer>> big = new ArrayList<>();
big.add(r0);
big.add(r1);
big.add(r2);
big.add(r3);
System.out.println(test2.canVisitAllRooms(big));
System.out.println(visited);
}
}
编程愉快！