ddu 1010 Tempter of the Bone

ddu 1010 Tempter of the Bone"/>

ddu 1010 Tempter of the Bone

该题是一个典型的搜索题，

代码如下

#include<stdio.h>
#include<math.h>
#include<string.h>
int a,b,c,d,n,m,T;
char map[10][10];    //地图数组 
int biao[10][10];// 标记访问数组 
int dx[]={0,0,1,-1};//控制左右上下的移动坐标变化； 
int dy[]={-1,1,0,0};
int sou(int x,int y,int t)      //所在位置的量  和已走的时间 
{int i;if(t==T)          //是否存在t时刻恰好是终点 {if(map[x][y]=='D')return 1;else return 0;}if((T-t+c-x+d-y)%2)        //剪枝 return 0;int e,f;     				//定义下一个位置坐标的量e f  for(i=0;i<4;i++){e=x+dx[i]; 				//走到下个位置 f=y+dy[i];if(e>=n||f>=m||e<0||f<0||biao[e][f]||map[e][f]=='X')     //查看是否越出nm界面 continue;biao[e][f]=1;         //标记访问过的为1； if(sou(e,f,t+1))       //枚举下一个位置 return 1;biao[e][f]=0;        //回退恢复 }return 0;
}
int main()
{int i,j;while(~scanf("%d%d%d",&n,&m,&T)&&n!=0&&m!=0&&T!=0)//输入长宽和时间； {getchar();//吃掉空字符； for(i=0;i<n;++i){scanf("%s",map[i]);//一次性二维字符数组的一行   for(j=0;j<m;j++)//改变j来查看 {if(map[i][j]=='S')//查看是否为起点 {a=i;b=j;   //起点坐标 }else if(map[i][j]=='D')//查看是否为终点 {c=i;d=j;         //终点坐标 }}}memset(biao,0,sizeof(biao));    //将标记数组的初始化为0 biao[a][b]=1;                    //将七点设为访问过 if(sou(a,b,0))						//调用递归函数 printf("YES\n");else printf("NO\n");}return 0;
}