【问题描述】
有个桌子长 R 宽 C,被分为 R*C 个小方格。其中,一些方格上有箱子,一些方格上有按 钮,一些方格上有障碍物,一些方格上是空地。现在有个任务,需要把所有箱子推到这些按 钮上面。箱子有个特征,只能推不能搬不能拉。现在需要用最少的步数把所有箱子推到按钮 上。 当然,箱子和人都只能以格子为单位移动,不存在一部分在格内一部分在格外的情况; 只能向四个方向推,箱子和推箱子的队员都不能穿越障碍物。推动的定义是,人的前进方向 被箱子挡住,且箱子在顺着前进方向的下一格不是箱子或者障碍物,那么就可以推着箱子和 箱子一起前进一步。
【输入文件】
输入第一行有两个整数 R,C(4<=R,C<=7),代表桌子的长和宽,接下来一共有 R 行,
每行有 C 个字符。
字符的含义:
0:代表空地
1:代表障碍物
2:代表箱子
3:代表按钮
4:人所在的初始地方
输入数据保证障碍物环绕整个地图,箱子数目跟按钮数目相同,箱子最少有一个,不 会超过 3 个,队员肯定只有一个。不用考虑箱子初始就按着按钮的情况。保证有解
【输出文件】
输出只有一行,为解决机关的最小步数。
【输入样例】
4 5
11111
14231
10231
11111
【输出样例】
4
【样例说明】 在样例中,最快的方法之一是先向东把第一个箱子推到按钮上,然后向西走
回原处,之 后向南一步,再向东推第二个箱子到按钮上。至此任务完成,共使用了 4 步。
【数据范围】
对 30%的输入数据 :箱子只有一个。
对 100%的输入数据 :4<=R,C<=7
题解
用 dist[position][box1][box2][box3]记录人在 position,箱子 1 在 box1,箱子 2 在box2,箱子 3 在 box3 位置时最少需要花费的步数。Bfs 一遍即可。
首先的问题是box1怎么记录两个值(坐标嘛)so我们就记录一个值,行号脱离出去(未完待续,太困了)
那么上代码
诶?代码呢?
作者已经困死在了调试板前
so等作者什么时候醒了再说吧
那么考试时发生了什么?
也行low逼作者考试前听了梁静茹的勇气,于是有了勇气写30分大bfs
结果还是搜爆了(全是错的,什么样例也过不了)
然而作者仍不死心,觉得可以把搜索分成两大部分
就先dfs出了人到箱子的上下左右方向不同的路程,(这部分就是个走迷宫的板嘛)再开始玄学搞事
搞着搞着搞了10分
聊胜于无了
ps(这道题应该妥妥第三题的)