Tempter of the Bone——DFS(王道)
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
#include <iostream>
#include<cstdio>
using namespace std;
char maze[][];//保存地图信息
int n,m,t;//地图大小n*m,起点到终点能否恰好为t
bool success;//是否找到所需状态标记
int go[][]={//s四个方向行走坐标差
-,,
,,
,,
,-
}; void DFS(int x,int y,int time){
for(int i=;i<;i++){
int nx=x+go[i][];//枚举四个相邻位置
int ny=y+go[][i];
if(nx< || nx>n || ny< || ny>m)//地图外
continue;
if(maze[nx][ny]=='X')//碰墙
continue;
if(maze[nx][ny]=='D'){//到终点
if(time+==t){//所用时间恰好为t
success=true;//搜索成功
return;
}
else
continue;
}
maze[nx][ny]='X';//该点设为墙
DFS(nx,ny,time+);//递归扩展该状态
maze[nx][ny]='.';//把原来的路改回来
if(success)
return;
}
} int main(){
while(scanf("%d %d %d",&n,&m,&t)!=EOF){
if(n== && m== && t==)
break;
for(int i=;i<=n;i++)
scanf("%s",maze[i]+);
success=false;
int sx,sy;
for(int i=;i<=n;i++){//寻找D的坐标
for(int j=;j<=m;j++){
if(maze[i][j]=='D'){
sx=i;
sy=j;
}
}
}
for(int i=;i<=n;i++){//找到S后,判断S和D的奇偶关系是否和t相符
for(int j=;j<=m;j++){
if(maze[i][j]=='S' && (i+j)%==((sx+sy)%+t%)%){
maze[i][j]='X';//起始点设为墙
DFS(i,j,);//递归扩展初始状态
}
}
}
puts(success==true?"YES":"NO");
}
return ;
}
//说实话我真的不是很懂43行,为什么要+1。。。请在评论区告诉我,多谢!
最新文章
- JS函数 -- 功能,语法,返回值,匿名函数,自调用匿名函数,全局变量与局部变量,arguments的使用
- Repeater——数据库控件学习
- Autowired properities class
- MVC4建立DBContext的EF6数据
- hdu1573:数论,线性同余方程组
- [转]如何正确设置nginx中remote_addr和x_forwarded_for参数
- html form表单提交数据并后台获取
- 《深入理解OSGi:Equinox原理、应用与最佳实践》笔记_2_建立开发环境
- EL表达式 requestScope initParam用法
- 外观模式(Facade)
- SQL Server 2005的服务器角色(public)的问题
- java集合-HashMap源码解析
- 常用的JVM调优参数总结汇总【随时查阅学习】
- [CQOI2017]小Q的表格(数论+分块)
- 数据预处理:独热编码(One-Hot Encoding)
- eclipse打war包编译文件不更新
- vue实例的方法
- RabbitMQ集群下队列存放消息的问题
- Redis 的线程模型
- stat命令的实现-mysate
热门文章
- Linux添加用户并赋予/取消管理员权限
- sublime text3中使用Emmet部分标签无法闭合
- <;松本行弘的程序世界>; 读书笔记
- easyui中导航菜单accordion与tree的动态添加
- CF 1003C Intense Heat【前缀和/精度/双层暴力枚举】
- 20180824Noip模拟赛10分总结
- hdu6070
- 并查集【p1197】[JSOI2008]星球大战
- SPOJ CIRU - The area of the union of circles (圆的面积并)
- POJ 3281 Dining(网络流)