题目 http://acm.hdu.edu.cn/showproblem.php?pid=1010
刚开始拿着这个题目 开始用bfs 但是一提交就错 不知道为什么 很纠结哦
但是最后还是看别人解题报告才知道哦
题意 是给一个起点 S 总点D 求S 到 D点的距离哦 但是时间要切好等于 t 时，
奇偶剪枝：
是数据结构的搜索中，剪枝的一种特殊小技巧。
现假设起点为(sx,sy)，终点为（ex,ey），给定t步恰好走到终点，
| s | ||||
| | | ||||
| | | ||||
| | | ||||
| + | — | — | — | e |
如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；
| s | — | — | — | |
| — | — | + | ||
| | | + | |||
| | | ||||
| + | — | — | — | e |
如图，为一般情况下非最短路径的任意走法举例，step2=14；
step2-step1=6，偏移路径为6，偶数（易证）；
故，若t-[abs(ex-sx)+abs(ey-sy)]结果为非偶数（奇数），则无法在t步恰好到达；
返回，false；
反之亦反。
下面给出ac代码哦
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[7][7];
int dre[4][2]={0,1,1,0,0,-1,-1,0};
int n,m,t,sx,sy,ex,ey,flag;
void dfs(int x,int y,int time)
{
if(flag==1) return ;
///t-[abs(ex-sx)+abs(ey-sy)]结果为非偶数（奇数），则无法在t步恰好到达
if(time<abs(ex-x)+abs(ey-y)||(time-(abs(ex-x)+abs(ey-y)))%2) return ;
if(time==0) ///t代表剩余时间，每走一步t--，这里若t=0，则迷宫坍塌
{
if(ex==x&&ey==y){ flag=1; return ;}
else return ;
}
else for(int i=0;i<4;i++) ///上右下左查询
{
int nx=x+dre[i][0];
int ny=y+dre[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<=m&&(a[nx][ny]=='.'||a[nx][ny]=='D'))
{
a[nx][ny]='X';
dfs(nx,ny,time-1); ///搜索
a[nx][ny]='.'; ///回溯
}
}
return ;
}
int main()
{
int i,j;
while(cin>>n>>m>>t,n+m+t)
{
int count=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S'){sx=i,sy=j;}
else if(a[i][j]=='D'){ex=i,ey=j;}
else if(a[i][j]=='.') count++; ///记录如果全走多少步
}
}
if(count+1<t) ///总共可以走的步数如果比给定时间还少
{
cout<<"NO"<<endl;
continue;
}
flag=0;
dfs(sx,sy,t);
if(flag){cout<<"YES"<<endl; continue;}
else {cout<<"NO"<<endl; continue;}
}
return 0;
}