#1991. Pku2422 The Wolves and the Sheep

题目描述

三只狼和一只羊在一片草地上相遇了~ 群狼很饥饿,后果很严重…… 草地是一个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。