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;
}
更多推荐
ddu 1010 Tempter of the Bone
发布评论