#P3858. [TJOI2008] 贪吃蛇
[TJOI2008] 贪吃蛇
题目背景
佳佳和金明在玩一个新版的对战型贪吃蛇游戏:在一个长方体中,某些格子是障碍物,其余的格子里都有食物。佳佳把贪吃蛇放到其中一个有食物的格子中,然后金明控制贪吃蛇移动一步到相邻的有食物的格子中,然后佳佳再控制它移动一步,就这样双方轮流进行下去。要注意的是移动的时候只能向上下左右前后的六个方向之一移动,且不能走出长方体的边界(当然,有障碍物的格子也是不能走的)。并且游戏要求贪吃蛇每步都必须能吃到新的食物,即不能走回以前经过的格子(包括起点也不能走回)。游戏进行到某方不能再按照上述规则移动蛇时,这一方就输掉了。
题目描述
佳佳和金明都是十分聪明的孩子,他们在游戏中总是会选择对自己最有利的策略。因为贪吃蛇的初始位置是由佳佳指定的,现在佳佳想知道,能不能找到这样一个初始位置使得自己一定可以获胜呢?
输入格式
输入文件的第一行包含一个整数N,表示此文件包含的测试样例数。接下来就是N组样例的描述。
每组样例描述的第一行包含三个整数H,R,C,表示长方体的高度,长度和宽度。接下来是H个R行C列的矩阵,每个矩阵描述此长方体的一层。矩阵包含的字符只有’.’和’X’两种,其中’.’表示初始时有食物的格子,’X’表示障碍。这H个矩阵描述之间都用一个空行隔开。
输出格式
输出N行,表示对应的游戏中佳佳是不是一定可以获胜。如果佳佳可以获胜,输出“yes”,否则输出“no”。
2
2 2 3
...
X.X
X.X
XXX
2 2 3
.X.
.X.
.X.
.X.
yes
no
提示
对于40%的数据,H * R * C ≤ 16
对于100%的数据,H * R * C ≤ 100, N ≤ 10
输入数据保证每个长方体至少包含一个不是障碍物的格子。