本文共 2206 字，大约阅读时间需要 7 分钟。

今天学习奇偶剪枝技巧（DFS）

题目大意与思考：

这题说在这个地图中，给你个时间 t ，出口的大门会每隔 t 秒钟打开一次，问你能不能从这个地图中离开。而且这个地图中的位置经过了一次就不能经过第二次。

算法分析：

单纯的算法来看，这题是一道典型的搜索问题。那能不能是 BFS呢？肯定不行，因为 BFS虽然是最短的时间到达出口，但是最短的时间并不一定能赶上大门打开的时间。然而就需要试探、回溯、那么肯定就是用 DFS了！

如何设计 DFS算法呢？一开始的时候大门是关闭的，每 t 秒钟会打开一次，也就是说，如果我到达终点并且大门是打开的，我就成功逃脱了！这时候结束递归。但是还有不成功的情况呢？什么情况是不成功的呢？

奇偶剪枝：

假设起点：start(sx, sy)，终点：end(ex, ey);

我们容易证明，在没有障碍的情况下，曼哈顿距离：abs(sx - ex) + abs(sy - ey)是从起点到终点的最短距离！ 如果我们想要在 t 步的时候走到终点，我们就需要：

t - (abs(sx - ex) + abs(sy - ey)) 是一个偶数！

这个结论是怎么来的呢？

证明奇偶剪枝：

从上面的图我们可以理解，分情况讨论：

第一种情况：

同映射（0 -> 0 or 1 -> 1)

需要偶数步，也就是可达步数必须是偶数（step & 1 = 0） 同时，曼哈顿距离也是偶数

第二种情况：

异映射(1 -> 0 or 0 -> 1)

需要奇数步，可达步数必须是奇数（step & 1 = 1） 同时曼哈顿距离是奇数

综上所述：

如果我预期在 step 的步数（时间）内，到达终点（ex, ey）

那么我当前的位置（x, y）与终点的曼哈顿距离，必须与期望步数同奇偶性！ 所以：结论如下

step + (abs(x - ex) + abs(y - ey)) & 1 == 0

其中：step = Time - StepNow(预期总步数减去已经走掉了的步数)

Solving code:

#define _CRT_SECURE_NO_WARNINGS#include 
   
    #include 
    
     #include 
     
      const int maxn = 10;int n, m, t, vis[maxn][maxn], bx, by, ex, ey, ans, wall;int dir[4][2] = { {0, 1},{0, -1},{1, 0},{-1, 0} };char mp[maxn][maxn];void dfs(int x, int y, int step) {	if (x == ex && y == ey && 0 == step % t) {		ans = 1;		return;	}	int temp = abs(step - t) + (abs(x - ex) + abs(y - ey));	if (temp & 1) {		ans = 0;		return;	}	for (int i = 0; i < 4; i++) {		int dx = x + dir[i][0], dy = y + dir[i][1];		if (dx >= 0 && dx < n && dy >= 0 && dy < m && 'X' != mp[dx][dy]) {			if (!vis[dx][dy]) {				vis[dx][dy] = 1;				step++;				dfs(dx, dy, step);				step--;				vis[dx][dy] = 0;			}		}	}}int main() {	while (~scanf("%d %d %d", &n, &m, &t) && (n || m || t)) {		getchar();		ans = 0, wall = 0;		for (int i = 0; i < n; i++) {			scanf("%s", mp[i]);			for (int j = 0; j < m; j++) {				if ('S' == mp[i][j])					bx = i, by = j;				if ('D' == mp[i][j])					ex = i, ey = j;				if ('X' == mp[i][j])					wall++;				vis[i][j] = 0;			}			getchar();		}		if (n * m - wall <= t) {			printf("NO\n");			continue;		}		vis[bx][by] = 1;		dfs(bx, by, 0);		if (ans)			printf("YES\n");		else			printf("NO\n");	}	return 0;}
     
    
   

最后一点剪枝：

统计墙壁的数目，如果剩余的可走的位置小于等于需要走的步数，就必然走不通，小于可以理解，那为何是小于等于呢？？如果可走的位置恰恰等于需要走的步数，由于一开始狗狗所在的位置就不能再走，所以相当于可走的空间只有：

n * m - wall - 1 < t <=> n * m - wall <= t

转载地址：http://anmq.baihongyu.com/