[summary] detailed explanation of DFS common skills -- odd and even pruning


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.

    1. Parity pruning: for the current position (x, y), if the parity of T - sum and minn is different, prune.
    2. Accessibility pruning: if T - sum < Minn, prune.
    3. 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((t-sum)%2!=(Math.abs(x-ex)+Math.abs(y-ey))%2)	return;		//Parity pruning
		if(t-sum<Math.abs(x-ex)+Math.abs(y-ey))	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 Auto-generated 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(j-1);
					if(maps[i][j]=='S') {
						sx=i;
						sy=j;
					}
					if(maps[i][j]=='D') {
						ex=i;
						ey=j;
					}
				}
			}
			int minn = (Math.abs(sx-ex)+Math.abs(sy-ey));
			if((t-minn)%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");
		}
	}
}


114 original articles published, 55 praised, 8508 visited
Private letter follow

Tags: Java

Posted on Sat, 01 Feb 2020 00:15:57 -0800 by Rojay