有四個剪枝：
1、 已經找到一個符合要求的解；
2、 TIME至少要等于最短距離；
3、 TIME至多等于走遍除H之外的其他地方；
4、 這一個不是那么明顯，就是最短距離要和給定距離同奇偶。
其中剪枝1和4尤為重要，2和3這兩個顯而易見的剪枝并沒有起到多大的效果。純搜索可以拿50分，2、3、4依然只可以拿50分，1、2、3可以拿60分，只要有了1和4就可以AC。
以下是我的代碼：
#include<stdio.h>
long n,m,time,h,dx,dy,dis,i,j,ans,used[55][55];
char map[8][8];
long xd[]=
{-1,0,1,0};
long yd[]={0,-1,0,1};
void dfs(long x,long y,long dep)
{
long i,t1,t2;
if(dep>=time)
{
if(map[x][y]=='D')
ans=1;
return;
}
for(i=0;i<4;i++)
{
t1=x+xd[i];
t2=y+yd[i];
if(ans==0&&t1>=1&&t1<=n&&t2>=1&&t2<=m&&!used[t1][t2]&&(map[t1][t2]=='*'||map[t1][t2]=='D'))
{
used[t1][t2]=1;
dfs(t1,t2,dep+1);
used[t1][t2]=0;
}
}
}
int main()
{
scanf("%ld%ld%ld",&n,&m,&time);
getchar();
while(n!=0||m!=0||time!=0)
{
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
map[i][j]='#';
h=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%c",&map[i][j]);
if(map[i][j]=='H')
h++;
getchar();
}// Read
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j]=='D')
{dx=i;dy=j;}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
used[i][j]=0;
ans=0;
// Init
dis=dx+dy-2;
if(dis%2==time%2&&time>=dis&&time<=n*m-h)
dfs(1,1,0);
if(ans==1)
printf("Yes\n");
else printf("No\n");
// Run
scanf("%ld%ld%ld",&n,&m,&time);
getchar();
}
return 0;
}
posted on 2010-01-06 19:55
lee1r 閱讀(165)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索