题目：
问题描述
小狗在一个古老的迷宫中发现了一块骨头，这让他着迷了很多。然而，当他拾起它时，迷宫开始动摇，小狗可能感觉到地面下沉。他意识到骨头是一个陷阱，他拼命地试图走出这个迷宫。
迷宫是一个大小为N的矩形。在迷宫中有一扇门。一开始，门被关闭，并在短时间内（不到1秒）在第T秒打开。因此小狗不得不在第T秒钟到达门口。每一秒，他都可以将一个街区移到上，下，左，右相邻街区之一。一旦他进入一个街区，这个街区的地面就会开始沉没，并在下一秒消失。他不能在一个街区停留超过一秒钟，也不能进入访问区块。这只可怜的小狗能生存吗？请帮助他。
输入
输入由多个测试用例组成。每个测试用例的第一行包含三个整数N，M和T(范围打出来后面会显示不出来)分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局，每行包含M个字符。一个字符是以下之一：
‘X’：小狗不能进入的一堵墙;
‘S’：小狗的起点;
‘D’：门;要么
‘。’：空白块。
输入以三个0结束。这个测试用例不被处理。
产量
对于每个测试案例，如果小狗能够存活，则在一行中打印“是”，否则打印“否”。
示例输入
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
… d
0 0 0
示例输出
NO
YES
这是我第一个做的深搜题，讲一下我做这题的错误和进步过程
1：我最初只使用普通的搜索题，利用递归回溯可以找到结果。但是超时
2：看了网上的分析之后，才明白要剪枝，就是把不可能的情况减掉，我看了别人的剪枝，才知道原来两个点的奇偶性和走的步数的奇偶密切相关，即：偶数点到偶数点（坐标xy之和）需要走偶数次，奇数到奇数也要走偶数次。说明两点%2的结果如果相同就会走偶数次。相反则走奇数次，经过优化后if((x1 y1 x2 y2)%2 t%2==1) {return;}除了主要的这个，还想到了步数能不能到达，步数会不会超过所有路的问题。
3：发现还是超时，后来才想明白需要走一步剪枝规范去掉没用的，这样减少的次数是不仅仅初始的那个状态。这样优化后理论上可以ac
4：但是我依然超时，做了很多尝试，发现我的dfs函数的参数过多，我把他写在外面静态区域，就成功ac了。可以看代码
代码如下：（被注释部分代码就是超时而没法过的最初形式）
import java.util.Scanner; public class Main { static int d[][]= {{-1,0},{0,-1},{1,0},{0,1}};//上左下右 static boolean judgle=false; static int n,m,t,x2,y2; public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()) { n=sc.nextInt();//行数 m=sc.nextInt();//列数 t=sc.nextInt();//门打开的时间 sc.nextLine(); if(n==0&&m==0&&t==0)break; char a[][]=new char[n][m]; boolean b[][]=new boolean[n][m];//判断是否有障碍 boolean c[][]=new boolean[n][m];//走过记录 int x1=0,y1=0; for(int i=0;i<n;i++)//赋值 { String exa=sc.nextLine(); a[i]=exa.toCharArray(); } for(int i=0;i<n;i++)//赋值 { for(int j=0;j<m;j++)//赋值 { if(a[i][j]=='X') {b[i][j]=true;}//有障碍 else if(a[i][j]=='S') {x1=i;y1=j;}//起点 else if(a[i][j]=='D') {x2=i;y2=j;}//结束点 } } c[x1][y1]=true; // if((x1+y1+x2+y2)%2+t%2==1) {judgle=false;} if(t>=m*n) {judgle=false;}//时间超了 // else if(t<Math.abs(y1-y2)+Math.abs(x2-x1)) {judgle=false;} // else { dfs(b,c,x1,y1);} if(judgle) {System.out.println("YES");judgle=false;} else {System.out.println("NO");} } } //private static void dfs( boolean[][] b,boolean c[][], int x1, int y1, int x2, int y2,int m,int n,int t) { private static void dfs( boolean b[][], boolean c[][], int x1, int y1) { if(t==0) {if(x1==x2&&y1==y2)judgle=true;return;} //到达终点 else if((x1+y1+x2+y2)%2+t%2==1) {return;} else if(t<Math.abs(y1-y2)+Math.abs(x2-x1)) {return;} else { for(int i=0;i<4;i++) { int x=x1,y=y1; if(x1+d[i][1]<0||y1+d[i][0]<0||x1+d[i][1]>=n||y1+d[i][0]>=m){continue;}//不越界 else { if(!b[x1+d[i][1]][y1+d[i][0]]&&!c[x1+d[i][1]][y1+d[i][0]]) //you障碍 { x=x+d[i][1];y=y+d[i][0];t--;c[x][y]=true; if(t==0&&x==x2&&y==y2) {judgle=true;break;} dfs(b,c,x,y); c[x][y]=false;t++; } } } } } }
