ACM-ICPC寒假算法训练1：搜索 HDOJ P1010 : Tempter of the Bone 奇偶剪枝分析

2023-02-23 18:43:13

今天学习奇偶剪枝技巧（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 <cstdio>
#include <cmath>
#include <cstring>

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

码农公寓