Prune
 Pruning strategy is to use filtering conditions to cut out the search path that does not need to be considered (it has been judged that this path can not get the optimal solution) in the search process, so as to avoid some unnecessary search, greatly optimize the algorithm solution speed, and ensure the accuracy of the results.
 In short, it is to cut off some infeasible situations, such as using backtracking method when walking maze, backtracking at the same time when encountering dead Hu, resulting in long running time of the program. In fact, the concept of pruning is similar to walking in a maze to avoid a dead end. If we regard the search process as the traversal of a tree, pruning, as the name implies, is to cut off some "dead ends" in the tree, which cannot reach the solution we need, so as to reduce the search time.
Parity pruning
Consider the matrix as follows: (0 and 1 represent parity) 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 Take a step from the grid of 0 to the grid of 1. Take a step from the grid of 1 to the grid of 0. That is to say: from 0 to 1, it must be an odd step, from 0 to 0, it must be an even step. So when it comes to going from 0 to 0 (from 1 to 1), but the required time is odd Or from 1 to 0 (from 0 to 1), but the required time is even Can be directly judged not reachable! For example, there is a map: S... .... .... .... ...D The minimum distance from S to D is s = abs ( dx  sx ) + abs ( dy  sy ) If there are obstacles in the map that cannot be passed by: S..X XX.X ...X .XXX ...D Minimum distance at this time s' = s + 4 If you get around the obstacles, you'll deviate from the original route, but no matter how many points you deviate, you will eventually return to the original route The offset distance is the shortest distance s plus an even distance (because one out and one in) It's like the matrix above You are required to go from 0 to 0. No matter how you circle, it is always the shortest distance (even steps) plus even steps You are required to go from 1 to 0, which can only be the shortest distance (odd steps) plus even steps Conclusion: the offset of the path is always even. Because the shortest path steps + offset (even number) = a feasible solution number Even + even = even, odd + even = odd Therefore, the parity of the steps of a feasible solution is determined by the steps of the shortest path That is to say, the parity of the shortest path step number and a feasible solution step number is the same
Example: [HDU]1010 Tempter of the Bone

Question meaning: whether the puppy can arrive at the destination D from the starting point S after the time T. '.' means the road that can be walked, 'Chen' means the wall that can'T be walked, 'S' means the starting position,' D 'means the ending position and can'T go back.

Train of thought: typical problems of odd and even pruning. Without pruning, you will be able to TLE. Let the shortest distance from the current position (x, y) to point D (dx, dy) be minn, it has taken time (steps) sum to reach the current position (x, y), and the time T required by the topic.
 Parity pruning: for the current position (x, y), if the parity of T  sum and minn is different, prune.
 Accessibility pruning: if T  sum < Minn, prune.
 Reachability pruning: if the difference between the given time and the shortest path at the beginning is not even or smaller than the shortest path, you can directly output "NO".
Code:
import java.util.Scanner; public class Main { static int n,m,t,sx,sy,ex,ey; static boolean flag; static int[][] dir = {{1,0},{1,0},{0,1},{0,1}}; static boolean[][] vis = new boolean[10][10]; static char[][] maps = new char[10][10]; static void dfs(int x,int y,int sum) { if(flag) return; //Jukeng, without this sentence, you will be TLE if(maps[x][y]=='D' && sum==t) { flag=true; return; } if((tsum)%2!=(Math.abs(xex)+Math.abs(yey))%2) return; //Parity pruning if(tsum<Math.abs(xex)+Math.abs(yey)) return; //Reachability pruning for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy] && maps[xx][yy]!='X') { vis[xx][yy]=true; dfs(xx,yy,sum+1); vis[xx][yy]=false; } } return; } public static void main(String[] args) { // TODO Autogenerated method stub Scanner cin = new Scanner(System.in); while(cin.hasNext()) { flag=false; for(int i=0;i<=8;i++) for(int j=0;j<=8;j++) { vis[i][j]=false; maps[i][j]='0'; } n = cin.nextInt(); m = cin.nextInt(); t = cin.nextInt(); if(n==0 && m==0 && t==0) break; for(int i=1;i<=n;i++) { String str = cin.next(); for(int j=1;j<=m;j++) { maps[i][j] = str.charAt(j1); if(maps[i][j]=='S') { sx=i; sy=j; } if(maps[i][j]=='D') { ex=i; ey=j; } } } int minn = (Math.abs(sxex)+Math.abs(syey)); if((tminn)%2==1  t<minn) { //Parity pruning System.out.println("NO"); continue; } vis[sx][sy]=true; dfs(sx,sy,0); if(flag) System.out.println("YES"); else System.out.println("NO"); } } }