May 1

传教士与食人魔的故事 不指定

felix021 @ 2008-5-1 02:14 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3687) | Via 本站原创 | |
2008年4月27日第二届中南地区程序设计邀请赛(国防科技大学)决赛B题
Problem B - The missionaries and cannibals

Desciption
The missionaries and cannibals problem is usually stated as follows: Three missionaries and three
cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way
to get everyone to the other side, without ever leaving a group of missionaries in one places
outnumbered by the cannibals in that place. Now the problem has been extended to be more
complicated. There are m missionaries and m cannibals who want to cross the river. And the boat is
also enlarged to be capable of supporting n people. In order to make all of them cross the river safely,
what s the least number of steps? Notice that when the boat goes across the river there must be at
least one missionariy o cannibal on the boat.

Input
The first line of the input is an integer T which indicates the number of test cases. Each test case is
specified on a separate line and is made of two positive number m and n, where m <= 100000 and
n <= 1000.

Output
For each test case, output the result on a single line. If the problem can't be solved, print -1 as the result.

Sample Input
2
3 2
20 3

Sample Output
11
-1

Hint (added by felix021)
For sample input "3 2", the least steps are:
3 2
STEP    LEFT(M C)   BOAT             Right(M C)
Step=0  3 3 |<=>    | 0 0
Step=1  3 1 |    <=>| 0 2
Step=2  3 2 |<=>    | 0 1
Step=3  3 0 |    <=>| 0 3
Step=4  3 1 |<=>    | 0 2
Step=5  1 1 |    <=>| 2 2
Step=6  2 2 |<=>    | 1 1
Step=7  0 2 |    <=>| 3 1
Step=8  0 3 |<=>    | 3 0
Step=9  0 1 |    <=>| 3 2
Step=10  0 2 |<=>    | 3 1
Step=11  0 0 |    <=>| 3 3


题意给得实在不清楚,为了能够更好的理解这个问题(以及样例输入3 2的过程),先看看下面这一段,是这个故事的原型:

引用

摘自: http://www.cppblog.com/sicheng/archive/2008/04/04/46267.html
(这篇文章里给出了这题的DFS, BFS, 迭代DFS和AStar算法,但是好像还是处理不了这么大的数据)
传教士与食人魔的故事
1.题目描叙:
Three missionaries and three cannibals come to a river. A rowboat that seats two is available.
If the cannibals ever outnumber the missionaries on either bank of the river, the missionaries will be eaten.
How shall they cross the river?



比赛的时候因为忘了故事的原型,所以一直没弄懂,直到最后问了Judge才明白,觉得用BFS搜蛮简单,尝试着写了一点代码,但是没来得及写完。
今天晚上拿出题目重新看了看,开始认真的写,然后才发现自己真是低估了这题。
一则这题的数据量实在太大了,以致于稍大一些的输入就会出现满队列(BFS)的情况;
二则剪枝也不容易,我只做了最简单的剪枝,就是不返回上一步,但是要如何才能不返回已经展开过的节点,暂时还没有思路(需要的空间太大了)
不过最后好歹实现了这个程序(Felix第一次脱离任何教程自己写搜索哦~),能够算出比较简单的数据并给出路径。
这里附上代码吧,期待大牛的指点。
下载文件 (已下载 530 次)





欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]