提示: 欢迎访问OurACM平台。
Problem 2196 Escape

Accept: 327    Submit: 1701
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小明进入地下迷宫寻找宝藏,找到宝藏后却发生地震,迷宫各处产生岩浆,小明急忙向出口处逃跑。如果丢下宝藏,小明就能迅速离开迷宫,但小明并不想轻易放弃自己的辛苦所得。所以他急忙联系当程序员的朋友你(当然是用手机联系),并告诉你他所面临的情况,希望你能告诉他是否能成功带着宝藏逃脱。

Input

有多组测试数据。

每组测试数据第一行是一个整数T,代表接下去的例子数。(0<=T<=10)

接下来是T组例子。

每组例子第一行是两个整数N和M。代表迷宫的大小有N行M列(0<=N,M<=1000)。

接下来是一个N*M的迷宫描述。

S代表小明的所在地。

E代表出口,出口只有一个。

.代表可以行走的地方。

!代表岩浆的产生地。(这样的地方会有多个,其个数小于等于10000)

#代表迷宫中的墙,其不仅能阻挡小明前进也能阻挡岩浆的蔓延。

小明携带者宝藏每秒只能向周围移动一格,小明不能碰触到岩浆(小明不能和岩浆处在同一格)。

岩浆每秒会向四周不是墙的地方蔓延一格。

小明先移动完成后,岩浆才会蔓延到对应的格子里。

小明能移动到出口,则小明顺利逃脱。

Output

每组测试数据输出只有一行“Yes”或者“No”。 “Yes”代表小明可以成功逃脱。否则输出“No”。

Sample Input

3 5 5 ....! S.... #.... !#... #E... 2 2 S. !E 2 2 SE !.

Sample Output

Yes No Yes

Source

福州大学第十二届程序设计竞赛

Submit  Back  Status  Discuss