3568考虑DFS从S出发但是否应该有vis数组可行路径可能包括可以重复走过的路甚至可能是唯一解比如L S L. X .或许考虑二分法验证这个步数下能否收集到所有垃圾但这样的话依然需要一个最优的路径才能知道当前的步数是否可行本质还是直接寻找最少步数继续考虑DFS如果不考虑vis最主要的是可能陷入死循环比如L SR .等出现正方形循环的状态而由于可以走重复路径即折回去的存在BFS又不可行或许BFS可行虽然死循环依旧存在但是是放在队列当中,每次BFS时的步数都是在增大可以设置出一个上限然后一旦收集到了所有垃圾那就直接结束了那BFS队列里的状态就是当前位置和能量以及目前收集到的垃圾数量每个步数的处理检测当前位置所有可走的格子排除X和边界然后处理格子的状态如果是R就将下个位置的能量为满如果为L就让已收集垃圾1但这样有一个致命问题就是无法标记垃圾的状态即相同的垃圾可能会被重复收集多次然后造成误判但又不能直接删除因为是BFS考虑图的可达性比如S到所有L和R的距离然后R到所有R和L的距离编号最后如果能连城一个图结果就不是-1否则先是-1然后再在这个图里找最小路但这样的图又如何构建AI就是说对于垃圾的状态是存完整的信息不过不用数组而是二进制这就是所谓状态压缩