请教百度程序大赛《追捕游戏》算法，大家请进

melody

四个小孩正在花园里玩追捕游戏。一个小孩扮演逃亡者，其余三个小孩做追捕者。花园是一块由N行M列方格组成的草地，花园周围有木栏包围着，不能走出，花园里面还有一些障碍物不能够通过。游戏可以进行许多回合，每个回合分成两轮，第一轮追捕者可以进行追捕行动，第二轮逃亡者可以根据前一轮追捕者的行动开展逃亡旅程。在第一轮里，三个追捕者必须在三人中选择一个人向某个相邻的方格走一步，只有在三个人都没有可以走的相邻方格时，他们才允许选择停留在原地。在第二轮里，逃亡者也必须选择某个相邻的方格走一步，如果逃亡者没有任何可走的方格，那么逃亡者就被捕了。四个小孩都不允许走到有障碍物或其他人的方格上，也不能走出花园，因而，四个小孩总是会位于不同的方格上面。
这些小孩都是非常聪明的，三个追捕者也是团结一致的。追捕者如果有可以捉到逃亡者的方法，那么他们就一定不会错过。逃亡者如果有不被捕获的方法，那么他也不会犯错。除此之外，追捕者会希望尽快地捉到逃亡者，而逃亡者即使在会被捕获的情况下也会尽可能地拖延时间。给定花园的障碍物的分布图和四个小孩的初始位置，你知道追捕者有方法捉到逃亡者吗？如果有，他们要经过多少轮后才能捉到逃亡者呢？
基本要求：
输入：输入包含多组测试数据。每组测试数据第一行为两个整数N和M（1≤N≤10，1≤M≤10），为花园方格阵列的行数和列数。接下来N行，每行M个字符，可以为“.”、“#”、“O”和“X”，分别表示空地、障碍物、追捕者和逃亡者。追捕者总是会有三个，而且四个小孩一开始也都会在空地上面。
输出：每组测试数据输出一行，若追捕者能够捉到逃亡者，则输出他们要经过多少轮后才能成功。轮数的计算包括追捕者和逃亡者进行行动的两轮，逃亡者被捕获的那一轮不算，因而结果总是一个奇数。
我的邮箱bontaijun@hotmail.com请大家指教，谢谢拉

whb9633

......

melody

有谁帮。。帮。。。我。。。么

vat

你说说怎么做？不会没一点想法吧？
还有有没有Online Judge的网址给我（就是在线提交程序的地方或者测试数据也行）？

melody

这是网上搜到的出题人的说法：
很显然，这是个博弈问题，不过这个题不能直接从初始状态开始BFS，因为很可能会BFS一个圈，回到原来的点。我们必须充分利用
“可以走到对方一个必败状态点是我方的必胜状态点”，“无论如何都会走到我方必胜状态点的是对方的必败状态点”。所以，从
对方的必败状态点开始反向BFS是个很明智的方法，这样可以找出所有我方的必胜状态点，而没有被BFS到的我方的点当然就是平手
状态点了。

melody

基本要求：
输入：输入包含多组测试数据。每组测试数据第一行为两个整数N和M（1≤N≤10，1≤M≤10），为花园方格阵列的行数和列数。接下来N行，每行M个字符，可以为“.”、“#”、“O”和“X”，分别表示空地、障碍物、追捕者和逃亡者。追捕者总是会有三个，而且四个小孩一开始也都会在空地上面。
输出：每组测试数据输出一行，若追捕者能够捉到逃亡者，则输出他们要经过多少轮后才能成功。轮数的计算包括追捕者和逃亡者进行行动的两轮，逃亡者被捕获的那一轮不算，因而结果总是一个奇数。
样本输入：
2 2
OO
OX
3 3
OOO
##X
...
3 3
OO#
###
.OX
3 4
OO##
####
..OX
4 4
OOO.
....
....
...X
5 5
O...O
.....
..#..
.....
O...X
5 5
O...O
.....
...#.
.....
O...X
6 6
......
.O..O.
..##..
..##..
.O..X.
......
6 6
#.....
.O..O.
..##..
..##..
.O..X.
......
10 10
..........
..........
..O....O..
..........
..........
..........
..........
..O....X..
..........
..........
10 10
..........
.#.#.#.#.#
..O.....O.
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..O.....X.
.#.#.#.#.#
样本输出：
The escapee will be captured after 1 steps
The escapee will be captured after 7 steps
The escapee will be captured after 5 steps
The escapee will never be captured
The escapee will be captured after 21 steps
The escapee will never be captured
The escapee will be captured after 41 steps
The escapee will never be captured
The escapee will be captured after 39 steps
The escapee will never be captured
The escapee will be captured after 51 steps
进阶要求：
a)        输入/输出的图形化
b)        此问题实现算法并非唯一，请考虑其他实现可能，并比较不同算法之间的效率。

vat

我想这个问题的关键在于：
1。 逃跑者的策略
2。 追捕者的策略
必须规范问题中逃跑者的策略和追捕者的策略以减少搜算量，程序代码来说就是它的每一步是如何判定的（每一步不超过四个选择）

还有就是，是否存在逃跑者抓不到的情况。

melody

o,thinking~~