首页 > ACM题库 > HDU-杭电 > Hdu 1105 The Wolves and the Sheep-博弈[解题报告] C++
2013
11-28

Hdu 1105 The Wolves and the Sheep-博弈[解题报告] C++

The Wolves and the Sheep

问题描述 :

Nalim, Ocis and Remmarguts are playing on grass, and they feel very hungry now. As baby wolves, they decide to capture a little sheep to eat. Fortunately, they immediately discover a sheep roaming around the grass. However, what they found is the queen of the sheep —- Mmxl, who has extraordinary speed that can compare with the wolves, and is very clever! Can you judge whether the baby wolves will capture Mmxl!

There are some rules to follow:
The grass field is a rectangular area that consist of R * C grids. And some obstacles like stones or trees exist. The actions of the baby wolves and Mmxl are taken in rounds. In each round, baby wolves take actions first, and then Mmxl follows. In the baby wolves’ turn, the three wolves will make a decision, and choose one of them to move (a move means moving from a grid to a neighboring grid). There must be a wolf to move, unless none of them can move. In the Mmxl’s turn, she will always move. If she cannot move, she is captured. Baby wolves and Mmxl cannot move to the grids on which there are obstacles, and they are always on different grids. Baby wolves will never get out of the rectangular area. Once Mmxl gets away from the grass, she is never captured.

You should notice that the only situation that Mmxl is captured is that she cannot move, but is not that in wolves’ turn, some wolf is in the neighboring grid of Mmxl’s.

输入:

Input contains multiple test cases. Each test case starts with two numbers R and C (1 <= R, C <= 10) in one line. Then R lines follow, each line has C characters, which describes the grass field. A ‘.’ denotes an empty grid, an ‘X’ denotes an obstacle, a ‘W’ denotes a baby wolf, and a ‘S’ denotes the Mmxl. There are exactly three ‘W’ and one ‘S’. Every test case will be followed by a blank line.

输出:

There is only one line for each test case. If lovely Mmxl will not be captured in finity rounds, print "Lucky Mmxl is safe:)". If the wicked baby wolves are able to capture Mmxl, print "Poor Mmxl is in danger:(".

样例输入:

3 5
XXW.X
XWSWX
XXX.X
 
4 5
XXWXX
XWSWX
XX.XX
XX.XX
 
7 6
XXXXXX
XWWW.X
X....X
X....X
X....X
X...SX
XXXXXX
 
7 7
XXXXXXX
XWWW..X
X.....X
X..X..X
X.....X
X....SX
XXXXXXX
 
7 7
XXXXXXX
XWWW..X
X.....X
X..XX.X
X.....X
X....SX
XXXXXXX
 
10 10
WWW.......
..........
..........
..........
..........
.....S....
..........
..........
..........
..........
 
9 9
XXXXXXXXX
X...X...X
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX
 
9 9
XXXXXXXXX
X.......X
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX
 
9 9
XXXXXXXXX
....X....
XW.....WX
X.X...X.X
X..X.X..X
X...S...X
XXXXXXXXX
XWXXXXXXX
XXXXXXXXX
 
3 3
WX.
XSX
WXW

样例输出:

Lucky Mmxl is safe:)
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(
Lucky Mmxl is safe:)
Lucky Mmxl is safe:)
Poor Mmxl is in danger:(

题目大意:
在一个n*m的棋盘上(n,m<=10), 有一些地方是不可进入的障碍物。棋盘上有3只狼和一只羊,按回合制移动,狼先动,羊后动。
狼和羊都不可以进入障碍物或重叠(狼和狼的重叠以及狼和羊的重叠都是不允许的)。
在狼的回合里,三只狼中选一只狼动一格(上下左右),除非3只狼都不能移动,否则不允许不动。
在羊的会合里,羊上下左右移动一格,如果羊移动后逃出了棋盘,则羊胜利。如果羊无法移动,则狼胜利。
如果羊有一种策略可以使游戏永远进行下去,则也算是羊胜利。
给定初始棋盘,如果两方都按最优策略移动,求胜利者。
算法:
这明显是一道博弈搜索题目。但这个博弈搜索不同于一般的博弈搜索。这个博弈搜索的状态转移是有环的。例如狼往左,羊往左,然后狼往右,羊往右。于是状态又绕回来了。这个也是这道题目的关键所在。
其实我们可以倒过来考虑。考虑羊被困死的所有状态。如果知道所有这样状态的,那么我们就可以倒推一步,得到一个“狼一步后胜利”的狼必胜态列表,再倒退一步,得到“羊一步后必然被困死”的必输态列表。这样反复倒推,最终可以得出起点的属态。
但获得一个羊被困死的所有状态是很困难的。其实有一个比较巧妙地解决方法。就是我们依然从起点正向博弈宽搜,但搜索时并不计算这个状态的属性。一旦发现某个状态羊不能移动了(或移出棋盘了),我们就得到了一个必输(必胜)态,然后沿着这个状态倒推回去,把一路上可以算出属性的状态全部算出属性(如果这个状态是必输态,则它的父母(可能有多达16个)都是必胜态;如果一个状态是必胜态,则把它的父母的孩子数量减一,如果一个父母的孩子数量变成0了,则这个父母状态为必输态(这里的必胜必输都是相对于正在走棋的人而言的))。这样就免去了计算所有必输(必胜)态的困难。
但这样,状态数依然是N^4*M^4级别的,转移是3*4的(3只狼,4个方向),我们需要剪枝。注意到如果一个态的属性已经确定了,那么他所有的子态的属性也就确定了,而且如果起点在这个状态的子态中,那么也必然可以通过往前倒退到达起点。所以一旦一个状态属性被确定,就不需要扩展这个状态了。如果起点的属态确定了,那么就可以直接结束了。加上这个剪枝后实际上计算的状态数并不多,用hash表存储状态就没有问题了。
然后就是代码的问题了……细节很多,很恶心……要注意考虑到所有的情况。


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。