Kaitou Kid - The Phantom Thief (2)

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

破解字迷之后,你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石,并离开展馆。整个展馆呈矩形分布,划分为N*M个区域,有唯一的入口和出口(不能从出口进入,同样不能从入口出去)。由某个区域可直接移动至相邻四个区域中的一个,且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石,无需耗时。问至少要封锁几个区域(可以封锁放有宝石的区域,但不能封锁入口和出口)才能保证Kid无法完成任务。

Input

输入的第一行有一个整数C,代表有C组测试数据。每组测试数据的第一行有三个整数N,M,T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图,其中包括:

'S':入口
'E':出口
'J':放有宝石的区域,至少出现一次
'.':空白区域
'#':墙

Output

对每组测试数据,输出至少要封锁的区域数。

Sample Input

2 5 5 5 SJJJJ ..##J .JJJJ .J... EJ... 5 5 6 SJJJJ ..##J .JJJJ .J... EJ...

Sample Output

0 2

Hint

wangye

Source

2008杭电集训队选拔赛

提交代码