小明做了一個很久很久的夢，醒來后他竟發現自己和朋友在一個搖搖欲墜的大棋盤上，他們必須得想盡一切辦法逃離這里，
經過長時間的打探，小明發現，自己所在的棋盤格子上有個機關，上面寫著“你只有一次機會，出發后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"); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98371.html
標籤：其他