0_0_6233976_14154\Main.java:1: reached end of file while parsing
import java.util.*;public class Main{ public static int N,M,Time; public static char[][]map = new char[8][8]; public static boolean flag; public static int endX=0,endY=0; public static int op[][] = new int[4][2]; public static void main(String args[]) { Scanner cin = new Scanner(System.in); String strs[] = new String[10]; int startX=0,startY=0,count; initPosition(); while(true) { M = cin.nextInt(); N = cin.nextInt(); Time = cin.nextInt(); if(N==0&&M==0&&Time==0) break; initMap(); count=0; for(int i=1;i<=M;i++) { strs[i] = cin.next(); } for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { map[j][i]=strs[j].charAt(i-1); if(map[j][i]=='S') { startX=j;startY=i; } if(map[j][i]=='D') { endX=j;endY=i; } if(map[j][i]=='.') { count++; } } } if(count+1<Time) //如果空地个数小于时间则肯定不可能出去 { System.out.print("NO\r\n"); continue; } if((endX+startX+endY+startY)%2!=(Time%2)) //奇偶剪枝 { System.out.print("NO\r\n"); continue; } flag = false; dfs(startX,startY,0); if(flag) { System.out.print("YES\r\n"); } else { System.out.print("NO\r\n"); } } } public static void dfs(int x,int y,int time) { if(flag) //若已经得到答案则直接返回 return; if(Math.abs(x-endX) + Math.abs(y-endY) > Time - time) //离终点的坐标距离大于剩余时间则肯定不能到达 return; if(map[x][y]=='X') return; map[x][y] = 'X'; for(int i=0;i<4;i++) { int X = x + op[i][0]; int Y = y + op[i][1]; if(map[X][Y] == '.') { dfs(X,Y,time+1); //往下搜索,time+1 } if(map[X][Y]=='D'&&time+1==Time) //判断下一个是否是终点 { flag = true; return; } } map[x][y] = '.'; } public static void initMap() //初始化地图 { for(int i=0;i<8*8;i++) { map[i%8][i/8]='X'; } } public static void initPosition() //初始化运动方向 { op[0][0] = 1; op[0][1] = 0; op[1][0] = -1; op[1][1] = 0; op[2][0] = 0; op[2][1] = 1; op[3][0] = 0; op[3][1] = -1; }}
|