Preparing NOJ

天神小学

1000ms 65536K

Description:

corpse partyblood drive》中有这么一段,班长筱崎亚由美拿到六鬼门的晶石,导致了涅?的暴走,天小的崩溃,靠着幸子的力量才逃出了天小。(剧情什么的不重要)

现在我们假设没有幸子,班长需要靠自己的力量逃出天神小学。可以把天神小学看作是一个二维的迷宫,每一秒都只能从当前位置走到上下左右四个相邻的格子里,因为天小一直在崩溃,所以有很多点是无法行走的。问班长能不能在天小完全崩溃,即t秒内逃出天神小学。

Input:

第一行一个整数T,表示数据组数

每组数据第一行输入3个整数nmt分别表示迷宫的行数,列数,以及距离天小崩溃剩余的时间。(3≤n,m≤20,t≤100)

接下来输入n行,每行有一个长度为m的字符串。

其中字符’.’表示可以通行

字符’*’表示无法通行

字符’O’表示出口

字符’X’表示班长的起始位置


Output:

若能逃离 输出 "happy end"

否则输出 "bad end"


Sample Input:

2

5 5 13
.....
.***.
.*X*O
.*.*.
...*.

5 5 14
.....
.***.
.*X*O
.*.*.
...*.

Sample Output:

bad end
happy end

Note:

本题由旧版NOJ导入,来源:kojimai

Info

NOJ

Provider NOJ

Code NOJ2076

Tags

Submitted 3

Passed 3

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet