神奇的奇偶性剪枝--HDU1010题解

可怜的小狗🐕

真是一道剪枝好题！！

普通暴力大家应该很好打吧。就不介绍了。

这里主要介绍神奇的奇偶性剪枝。

int path = abs(si-ei)+abs(sj-ej);

(si,sj) (ei,ej) 分别为起点终点坐标。我们可使用的两种剪枝方案是：

1. 如果所给的时间(步数) t 小于最短步数 path ，那么一定走不到。
2. 若满足t>path。但是如果能在恰好 t 步的时候，走到出口处。那么 (t-path) 必须是二的倍数。
   关于第二种方案的解释:

这种方案学名为“奇偶剪枝”。我们已知了最短的步数就是直角三角形的两条直角边，实际上的路径却不一定非要沿着这两条边走的。仔细看看只要是移动方向一直是右、下，那么走到的时候总步数也一定是 path 的。然而由于墙的存在或许我们不可能一直右、下的走下去。为了避开墙，我们可能会向左走，向上走等等。但为了到达目的地，你在最短步数的基础上，如果向右走了一步，那么某一时候也必须再向左走一步来弥补。所以 (t-path) 一定要是2的倍数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
const int dy[4] = {1,0,-1,0};
const int dx[4] = {0,1,0,-1};
int a[maxn][maxn],n,m,t,c,si,sj,ok,ei,ej;
char gtc()
{
	int c = getchar();
	while(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == '\b')c=getchar();
	return char(c);
}
void dfs(int x,int y,int d)
{
	if(ok||x<1||y<1||x>n||y>m||d>t)return;
#ifdef DEBUG
	printf("Visit dfs(%d,%d,%d) %d \n",x,y,d,a[x][y]);
#endif
	if(a[x][y]==3)
	{
#ifdef DEBUG
		printf("Visising D but d is %d \n",d);
#endif
		if(d==t)ok=1;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(a[xx][yy]==1||x<1||y<1||x>n||y>m)continue;
		if(a[xx][yy]!=3)a[xx][yy]=1;
		dfs(xx,yy,d+1);
		if(a[xx][yy]!=3)a[xx][yy]=0;
	}
}
int main(void)
{
	while(scanf("%d%d%d",&n,&m,&t) == 3)
	{
		memset(a,0,sizeof a);
		if(n == 0 && m == 0 && t == 0)return 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				c=gtc();
				switch(c)
				{
					case 'X': a[i][j]=1; break;//1 就是被访问 or 墙
					case 'S': a[i][j]=1; si=i;sj=j; break;
					case 'D': a[i][j]=3; ei=i;ej=j; break;
					default: break;//空地
				}
			}
		ok=0;
#ifdef DEBUG
		for(int i=1;i<=n;i++,puts(""))
			for(int j=1;j<=m;j++)
				cout<<a[i][j];
#endif
		int path = abs(si-ei)+abs(sj-ej);
		if(t<path||(t-path)&1)
			puts("NO");
		else
		{
			dfs(si,sj,0);
			if(ok)puts("YES");
			else puts("NO");
		}
	}
	return 0;
}