http://acm.hdu.edu.cn/showproblem.php?pid=1983 

              Kaitou Kid - The Phantom Thief (2) 
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) 
Total Submission(s): 28    Accepted Submission(s): 9 


Problem 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 
  

Author 
LL 
  

Source 
2008杭电集训队选拔赛 

想了很久，没好的办法去解决，大家有好的想法吗？ 谢谢。