一道很陈的搜索题了，深搜实现的，但我还是发现了一些之前没有注意的地方……
第一，全局变量的赋值应该注意……………………。
第二，就是搜索的优化剪枝问题，这种题很容易超时。
下面是代码：
#include<stdio.h> #include<string.h> #include<math.h> int dir[4][2]={-1,0,1,0,0,1,0,-1}; int n,m,t,si,sj,di,dj,wall=0,flag=0; char map[9][9]; void getmap() { int i,j; wall=0; for(i=0;i<n;i++) for(j=0;j<m;j++) { scanf("%1s",&map[i][j]); if(map[i][j]=='S'){ si=i; sj=j; } if(map[i][j]=='D'){ di=i; dj=j; } if(map[i][j]=='X')wall++; } } void dfs(int a,int b,int cnt) { int i,temp; if(a<0||b<0||a>n-1||b>m-1)return; if(a==di&&b==dj&&cnt==t) flag=1; if(flag) return; temp=t-cnt-abs(a-di)-abs(b-dj); //剪枝 if(temp<0||temp&1)return; //temp为负数或奇数时，无法到达 for(i=0;i<4;i++) { if(map[ a+dir[i][0] ][ b+dir[i][1] ]!='X') { map[ a+dir[i][0] ][ b+dir[i][1] ]='X'; dfs(a+dir[i][0],b+dir[i][1],cnt+1); map[ a+dir[i][0] ][ b+dir[i][1] ]='.'; } } return; } int main() { while(scanf("%d%d%d",&n,&m,&t),n) { wall=0; getmap(); if(n*m-wall-1<t) //剪枝 { printf("NO/n");continue; } flag=0; map[si][sj]='X'; dfs(si,sj,0); if(flag==1) printf("YES/n"); else printf("NO/n"); } return 0; }
