#P1991. Pku2422 The Wolves and the Sheep

    ID: 1014 传统题 3000ms 259MiB 尝试: 15 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-状态扩展图必胜/必败状态递推最小不动点迭代对称性去重状态编码位压缩存储

Pku2422 The Wolves and the Sheep

题目描述

三只狼和一只羊在一片 R×CR\times C 的草地上。每个格子是草地、石头或一只动物的初始位置。双方轮流行动,狼先行动。

每次移动一步只能沿上、下、左、右四个方向。动物不能进入石头格,也不能进入被其他动物占据的格子。狼不能离开棋盘。轮到狼时,三只狼中恰有一只移动。如果三只狼都无法移动,狼方跳过这一回合。轮到羊时,羊必须选择一个合法方向移动。

羊走到草地边界后可以从该边向外逃出。若羊一开始就在边界,它也一定能逃出。若轮到羊时它没有任何合法移动,狼方获胜。双方都采取最有利于自己的策略。判断狼方能否保证在有限步内获胜。

输入格式

输入包含不超过 1010 组数据,读到文件结束。每组第一行两个整数 R,CR,C。本站评测数据满足 1≤R,C≤101\le R,C\le10。

接下来 RR 行,每行 CC 个字符。英文句点 . 表示草地,X 表示石头,W 表示狼,S 表示羊。每组恰好有三只狼和一只羊。

输出格式

每组输出一行。如果狼方能保证获胜,输出 danger,否则输出 safe。

样例

4 5
..X.X
W..X.
....W
.SWX.
5 5
..WXS
W.WXX
...X.
.XX..
..X.X
4 4
.WW.
...S
.XX.
..W.
4 4
S..W
X.X.
....
..WW
5 5
...W.
.X...
XW..X
..S.X
.W...
5 5
XXXXX
X...X
XXW.X
XWWSX
XXXXX
5 4
X.W.
SXXW
..X.
.W..
X...
4 5
XXXXX
XS.WX
XWW.X
XXXXX
5 4
..X.
..X.
..X.
WX.S
W.W.
4 5
XXXXX
XW.SX
X.WWX
XXXXX

safe
safe
safe
safe
safe
danger
safe
danger
safe
danger