|
追捕 四个小孩正在花园里玩追捕游戏。一个小孩扮演逃亡者，其余三个小孩做追捕者。花园是一块由N行M列方格组成的草地，花园周围有木栏包围着，不能走出，花园里面还有一些障碍物不能够通过。游戏可以进行许多回合，每个回合分成两轮，第一轮追捕者可以进行追捕行动，第二轮逃亡者可以根据前一轮追捕者的行动开展逃亡旅程。在第一轮里，三个追捕者必须在三人中选择一个人向某个相邻的方格走一步，只有在三个人都没有可以走的相邻方格时，他们才允许选择停留在原地。在第二轮里，逃亡者也必须选择某个相邻的方格走一步，如果逃亡者没有任何可走的方格，那么逃亡者就被捕了。四个小孩都不允许走到有障碍物或其他人的方格上，也不能走出花园，因而，四个小孩总是会位于不同的方格上面。 这些小孩都是非常聪明的，三个追捕者也是团结一致的。追捕者如果有可以捉到逃亡者的方法，那么他们就一定不会错过。逃亡者如果有不被捕获的方法，那么他也不会犯错。除此之外，追捕者会希望尽快地捉到逃亡者，而逃亡者即使在会被捕获的情况下也会尽可能地拖延时间。给定花园的障碍物的分布图和四个小孩的初始位置，你知道追捕者有方法捉到逃亡者吗？如果有，他们要经过多少轮后才能捉到逃亡者呢？ 输入格式： 输入文件包含多组测试数据。每组测试数据第一行为两个整数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 说明： 共有5个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为5、10、15、30和40分，对每个测试数据集分别执行一次程序，每次必须在运行时限60秒内结束程序并输出正确的答案才能得分。 所有数据均从标准输入设备（stdin/cin）读入，并写出到标准输出设备 （stdout/cout）中。 五个测试数据集中输入N、M分别不大于6、7、8、9和10。 | 
IP卡
狗仔卡
发表于 2010-5-6 19:13
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
发表于 2011-10-4 01:46
