P0906

Pku2422 The Wolves and the Sheep

Pku2422 The Wolves and the Sheep

三只狼和一只羊在一片草地上相遇。狼群十分饥饿，试图围住羊。

草地是一个 R×CR\times C 的矩形网格。其中，字符 X 表示无法通过的石头，字符 . 表示草地，字符 W 表示狼，字符 S 表示羊。

狼方先行动，之后狼方与羊方交替行动。每次移动只能沿上、下、左、右四个方向之一，走到相邻的一格。动物不能进入石头所在的格子，也不能进入另一只动物当前占据的格子。

在狼方的回合中，狼方选择三只狼中的一只，使其合法移动一步。仅当三只狼都无法合法移动时，狼方才原地跳过该回合。

在羊方的回合中，羊必须合法移动一步。如果羊没有合法移动，则会被狼吃掉。如果羊从矩形边界向外移动并离开草地，则羊获救。

请判断狼方是否能保证在有限步内围住羊。

输入格式

输入包含多组测试数据，处理至文件末尾。

每组测试数据的第一行包含两个整数 R,CR,C，分别表示草地的行数和列数。

接下来 RR 行，每行包含 CC 个字符，描述草地。每组数据中恰有一个字符 S 和三个字符 W，其余字符只可能是 X 或 .。

输出格式

对于每组测试数据输出一行。

如果狼方能保证围住羊，输出 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

数据范围

  • 对于每组测试数据，1≤R,C≤101\le R,C\le 10；
  • 每组网格中恰有一个字符 S 和三个字符 W，其他格子只可能是 X 或 .；
  • 测试数据组数不超过 1010。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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