Felix021

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的过程），先看看下面这一段，是这个故事的原型：




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

---

欢迎扫码关注：

转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。