hdu1010 Tempter of the Bone （dfs）奇偶剪枝

題意：給定一圖，有入口出口，要求不能回頭的從入口走到出口，若能按指定的步數走到出口，輸出yes，否則輸出no

一開始沒看懂題意，以為是bfs，後來以為是一道普通的bfs題，交上去總是逾時，很郁悶，看了别人的思路，知道了有奇偶剪枝這東西，于是按照别人的思路，自己修修改改，終于a掉了，第一次做剪枝類的題目，有一些收獲。

奇偶剪枝：從起點（si，sj）到終點（di，dj）要求走t步，如果能走到，那麼t - （|si-di|+|sj-dj|）一定為偶數，，如果為奇數，不能走到終點。

以這個圖為例，所有點都用0，1填充，會發現，如果起點和終點數字是一樣的，那麼會走偶數步，，反之走奇數步。（|si-di|+|sj-dj|）為起點到終點的最小步數，

1.如果起點和終點數字一樣，都為0或1，任意走（|si-di|+|sj-dj|）步，且不走到終點，數字還是和起點終點相同的，此時在走到終點還是要走偶數步，設為extra（偏移量），如果要求t步走到終點，則（|si-di|+|sj-dj|）+ extra = t，即extra = t -（|si-di|+|sj-dj|）前面說過數字相同走偶數步，那麼extra必為偶數。

2..如果起點和終點數字不一樣，任意走（|si-di|+|sj-dj|）步，且不走到終點，數字和起點相反和終點相同，此時再走到終點仍然要走偶數步（|si-di|+|sj-dj|）+ extra = t，extra必為偶數

3.如果沒有多走，恰好t步走到，extra=0，為偶數

題目代碼：

#include<iostream>
#include<string.h>
using namespace std;
const int N=7,M=7;
int vis[N][M];
int n,m1,flag,t,wall;
char m[N][M];
int cul[]={1,0,-1,0,1};
int abs(int a)
{
	if(a<0)return -a;
	else return a;
}
void dfs(int i,int j,int di,int dj,int c)
{
	int extra=t-c-(abs(i-di)+abs(j-dj));
	if(extra<0||extra&1)
	return;
	if(c==t&&i==di&&j==dj)
	{
		flag=1;
	}
	if(flag)return;
	else
	{
		for(int k=0;k<4;k++)
		{
			int dx = i+cul[k];//   i+1,j   i,j+1  i-1,j   i,j-1
			int dy = j-cul[k+1];
			if(!vis[dx][dy]&&m[dx][dy]!='X'&&dx>=0&&dx<n&&dy>=0&&dy<m1)
			{
				vis[dx][dy]=true;
				dfs(dx,dy,di,dj,c+1);
				if(flag)return;
				vis[dx][dy]=false;
			}
		}
	}
}
int main()
{
	int si,sj,di,dj;
	while(cin>>n>>m1>>t&&(n!=0||m1!=0||t!=0))
	{
		wall = 0;
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++)
		for(int j=0;j<m1;j++)
		{
			cin>>m[i][j];
			if(m[i][j]=='S')
			{
				si=i;
				sj=j;
			}
			if(m[i][j]=='D')
			{
				di=i;
				dj=j;
			}
			if(m[i][j]=='X')wall++;
		}
			flag=0;
			if(m1*n-wall<=t)
			{
				cout<<"NO"<<endl;
				continue;
			}
			vis[si][sj]=true; 
			dfs(si,sj,di,dj,0);
			if(flag)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
	}
}