一个非常有意思的 BFS+DFS。附 数据。
本来今天的任务是多重背包,结果为了帮别人找WA点,自己也坑在这道题上了。
最后想了一组自己都没过的数据…发现想法都不正确…果断换思路了。
正确思路是以箱子为起点做BFS找最短。每次移动的时候DFS推断人能不能移动到箱子的后面。
開始就我写一个BFS,什么数据都过了。这组过不了
17 40 0 0 00 0 1 00 2 0 31 4 1 01 0 1 01 0 1 01 0 0 0
实际上答案是2.
我写的是总步数最短时,箱子的最短步数。给WA了。
然后我就换思路了,注意状态要用四维,由于可能存在要先把箱子推过去,然后再推回来的情况。
3 6
1 1 1 1 1 1
0 0 0 1 0 0
0 0 2 4 0 3
比方这样。
实际上是5.
#include #include #include #include #include #include #include