小明做了一个很久很久的梦，醒来后他竟发现自己和朋友在一个摇摇欲坠的大棋盘上，他们必须得想尽一切办法逃离这里。
经过长时间的打探，小明发现，自己所在的棋盘格子上有个机关，上面写着“你只有一次机会，出发后t秒大门会为你敞开”，而他自己所在的棋盘是大小为 N*M 的长方形，他可以向上下左右四个方向移动（不可走有障碍点）。棋盘中有一扇门。根据机关的提示，小明顿时明白了，他和朋友必须在第 t 秒到门口。而这一切，没有回头路！因为一旦他移动了，他刚才所在的点就会消失，并且他不能在一个点上停留超过一秒，不然格子会爆炸。大逃亡开始了，请问小明和朋友能安全的逃出这奇怪的棋盘吗？
Input
输入多组测试数据。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分别表示棋盘的大小和门打开的时间。接下来的N行给出棋盘布局，每一行包含M个字符。其中
".": 无障碍点
"X": 障碍点
"S": 起点
"D": 门
输入以 3 个 0 结束。这个测试用例不需要处理。
Output
对于每组样例输出一行。
如果小明能够安全逃出，输出 "YES" ，否则输出 "NO"。
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES 代码：
import java.util.Arrays;
import java.util.Scanner; public class Main{
static int n,m,T;
static final int N=10;
static int sx,sy,ex,ey;
static int dx[]={0,0,1,-1};
static int dy[]={1,-1,0,0};
static char map[][]=new char[N][N];
static boolean vis[][]=new boolean[N][N];
static boolean flag; static void dfs(int x,int y,int t){
//这种多if判断的一定加上return
if(flag) return; //已经找到一种走法
if(t>T) return; //大于要求的时间
if(T-t-Math.abs(x-ex)-Math.abs(y-ey)<0) return; //剩余的步数不足以到达终点
if((T-t)%2!=(Math.abs(x-ex)+Math.abs(y-ey))%2) return; //奇偶性一致
if(t==T && x==ex && y==ey){
flag=true;
} for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0 || yy<0 || xx>=n || yy>=m ||vis[xx][yy]) continue;
vis[xx][yy]=true;
dfs(xx,yy,t+1);
vis[xx][yy]=false;
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
n=scan.nextInt();
m=scan.nextInt();
T=scan.nextInt();
if(n==0 && m==0 &&T==0) break;
for(int i=0;i<n;i++) map[i]=scan.next().toCharArray();
for(int i=0;i<N;i++) Arrays.fill(vis[i],false);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(map[i][j]=='S'){
sx=i; sy=j;
}
else if(map[i][j]=='D'){
ex=i; ey=j;
}
else if(map[i][j]=='X')
vis[i][j]=true;
vis[sx][sy]=true;
flag=false;
dfs(sx,sy,0);
if(flag) System.out.println("YES");
else System.out.println("NO");
}
}
}