【问题描述】

有个桌子长 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(这道题应该妥妥第三题的)

05-11 22:11