Problem 1060 --C. 滑冰

1060: C. 滑冰

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 247  Solved: 39
[Submit][Status][Web Board][Creator:]

Description

冬天到了,身为北方人的Kajitsu喜欢在结冰的湖面上滑冰。
然而湖面上偶尔会有冰洞,Kajitsu担心会不小心滑进去。
我们用一个n*m的图表示湖面。
OOOOOOXOO
OOXOOKOUO
OOOOOOOXO
OOOXOUOOO
OOOOOXOOO
O:结冰的湖面。Kajitsu可以在上面自由穿过。
X:石头。当Kajitsu触及石头时,可以改变方向继续滑行。
U:洞窟。
K:Kajitsu的初始位置。
Kajitsu只能向着某一个方向一直滑行,直到碰到石头、掉入洞窟或者出界。
准确的说:
1.初始状态(Kajitsu位于'K')时,Kajitsu可以选择向上下左右任意方向滑行。
2.当Kajitsu的滑行遇到'X'时,Kajitsu停在'X'的前一格。(即按照Kajitsu滑行方向行进,遇到'X'的前一格)。此时Kajitsu可以选择向除原方向外任意方向滑行。
3.当Kajitsu滑行离开地图时,判定为Kajitsu已上岸,终止滑行。
4.当Kajitsu遇到'U'时,判定为Kajitsu已掉入洞窟,终止滑行。
现在Kajitsu想知道,对于给定的湖面,他是否有掉入洞窟的可能。

Input

第一行为两个数字 n m,用空格隔开
之后n*m描述一张地图(详见样例输入)
(0≤n,m≤10)

Output

如果Kajitsu有掉入洞窟的可能,输出“Dangerous”(不含双引号)

如果Kajitsu没有掉入洞窟的可能,输出“Safe”(不含双引号)

Sample Input

5 9
OOOOOOXOO
OOXOOKOXO
OUOOOOOOO
OXOOOOOOO
OOOXOXOOU

Sample Output

Dangerous

HINT


可按照以下路径掉入洞窟中(m为经过的路径)



OOOOOOXOO

OOXOOKOXO

OUmOOmOOO

OXmmmmOOO

OOOXOXOOU

Source

[Submit][Status]