Pku2422 The Wolves and the Sheep

时间限制:30s      空间限制:259MB

题目描述

三只狼和一只羊在一片草地上相遇了~ 群狼很饥饿,后果很严重…… 草地是一个R*C的矩形,矩形内“X”点代表石头是不能过的,“.”代表草地。狼用“W”表示,羊用“S”表示。 狼和羊交替的走,轮到狼走的时候,可以选择3只中的任意一只走一步,如果三只狼都走不动,那么可以不走。轮到羊走的时候,羊必须走。 如果某个时候羊不能走了,即它被围住了,那么羊就要被吃掉了,否则的话如果它逃出了草地,那么它就得救了。狼想知道他们能不能在有限步内围住羊然后美餐一顿。


输入格式

首先两个数R,C 接下来一个R*C的矩阵描述草地。 多组数据,处理到文件尾。


输出格式

如果狼能围住羊,打印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

提示

对于40%的数据保证 对于100%的数据保证 数据组数小于等于10。


题目来源

没有写明来源