http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目大意从S出发,问能否在时间t的时候到达终点D,X为障碍
需要注意的是要恰好在t时刻到达,而不是在t时间之内
深搜,注意剪枝 剩下格子大于t时间的时候剪掉这个很好想,但还是会超时,还有一个剪枝是依靠
奇偶性剪枝
比如地图依靠奇偶性是;
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1 可以发现偶数走一步一定到奇数,奇数走一步一定到偶数,所以当所在地的奇偶性与目的地D不一样的时候
一定走奇数步子,一样就走偶数步,判断这个来剪枝
code
#include <stdio.h>
#include <stdlib.h>
bool flag;
int n,m,t,i,j,x1,y1,x2,y2,num;
int dix[]={,,,-};
int diy[]={,,-,};
char str[][];
void DFS(int k,int l,int tc)
{
int i;
if(tc==t && k==x2 &&l==y2)
flag=true;
if(flag==true) return;
if (abs(x2-k)+abs(y2-l)>t-tc)return ; //两个回溯
if((abs(x2-k)+abs(y2-l))%!=(t-tc)%) return;
for(i=;i<;i++)
{
int dx=k+dix[i];
int dy=l+diy[i];
if(dx>= && dx<n && dy>= && dy<m && str[dx][dy]!='X')
{
str[dx][dy]='X';
DFS(dx,dy,tc+);
str[dx][dy]='.';
}
}
}
int main()
{
while (scanf("%d %d %d",&n,&m,&t))
{
getchar();
if(n==&&m==&&t==)
break;
num=;
flag=false;
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
scanf("%c",&str[i][j]);
if(str[i][j]=='S')
{
x1=i;y1=j;
}
else if(str[i][j]=='D')
{
x2=i;y2=j;
num++;
}
else if(str[i][j]=='.')
{
num++;
}
}
getchar();
}
str[x1][y1]='X';
if(num>=t)
DFS(x1,y1,);
if(flag==true)
printf("YES\n");
else
printf("NO\n");
}
return ;
}