小明作了一個好久好久的夢，醒來後他竟發現本身和朋友在一個風雨飄搖的大棋盤上，他們必須得想盡一切辦法逃離這裏。
通過長時間的打探，小明發現，本身所在的棋盤格子上有個機關，上面寫着「你只有一次機會，出發後t秒大門會爲你敞開」，而他本身所在的棋盤是大小爲 N*M 的長方形，他能夠向上下左右四個方向移動（不可走有障礙點）。棋盤中有一扇門。根據機關的提示，小明頓時明白了，他和朋友必須在第 t 秒到門口。而這一切，沒有回頭路！由於一旦他移動了，他剛纔所在的點就會消失，而且他不能在一個點上停留超過一秒，否則格子會爆炸。大逃亡開始了，請問小明和朋友能安全的逃出這奇怪的棋盤嗎？java
Input安全
輸入多組測試數據。每一個測試用例的第一行包含三個整數 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分別表示棋盤的大小和門打開的時間。接下來的N行給出棋盤佈局，每一行包含M個字符。其中
".": 無障礙點
"X": 障礙點
"S": 起點
"D": 門佈局
輸入以 3 個 0 結束。這個測試用例不須要處理。測試
Outputspa
對於每組樣例輸出一行。
若是小明可以安全逃出，輸出 "YES" ，不然輸出 "NO"。code
Sample Inputblog
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Outputclass
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"); } } }