Tempter of the Bone HDU - 1010(dfs)
Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 148156 Accepted Submission(s): 39500
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.
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES 题意:一个迷宫,要刚好在t秒的时候走到门口才可以,每一次走过一个格子就不能再走这个格子了,问可不可以走出来
思路:dfs搜索,如果时间t比所有格子的数量都多那肯定走不出来了,画一画就知道如果绕一绕的话肯定是增加偶数步的,那就可以进行剪枝了,如果不可以的话为了继续找寻路,记得把走过的那个点标记成未走过哦
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
typedef long long ll;
const int maxn = 1e2+;
const int mod = 1e9 + ;
int gcd(int a, int b) {
if (b == ) return a; return gcd(b, a % b);
}
int N,M,T,startx,starty,endx,endy;
char maze[maxn][maxn];
int dx[]={,,-,};
int dy[]={,,,-};
int step;
int ok;
void dfs(int x,int y,int step)
{
int temp;
if(x==endx && y==endy && step==T)
{
ok=;
return ;
}
if(x<= || x>N || y<= || y>M)
return ;
temp=abs(T-step)-(abs(x-endx)+abs(y-endy));
if(temp< || temp&)
return ;
for(int i=;i<;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(maze[nx][ny]!='X')
{
maze[nx][ny]='X';
dfs(nx,ny,step+);
if(ok)
return;
maze[nx][ny]='.';
}
}
return ;
}
int main()
{
while(scanf("%d%d%d",&N,&M,&T) && (N&&M&&T))
{
int num=;
for(int i=;i<=N;i++)
for(int j=;j<=M;j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S')
{
startx=i;
starty=j;
}
else if(maze[i][j]=='D')
{
endx=i;
endy=j;
}
else if(maze[i][j]=='X')
num++;
}
if(N*M-num<=T)
{
cout<<"NO"<<endl;
continue;
}
ok=;
maze[startx][starty]='X';
dfs(startx,starty,);
if(ok)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl; }
}
最新文章
- xcode8 info.plist文件中的各种权限。
- [问题解决]安装 SQL Server 无法开启NetFx3.5 的错误
- __getattribute__
- CSS3判断手机横屏竖屏
- Web开发中运行环境的配置:(Tomcat7.0.59)和开发环境的配置
- Java网络编程(TCP服务端)
- If-Modified-Since &; If-None-Match
- LoadRunner_Analysis(z) 分析
- HDU_1238——最大子串搜索
- Socket 学习(三).3 TCP UDP 图解
- SQL点滴1—SET QUOTED_IDENTIFIER OFF语句的作用
- scrapy爬虫 快速入门
- kubernetes系列09—Ingress控制器详解
- jexus System.BadImageFormatException Details: Non-web exception. Exception origin (name of application or object): App_global.asax_ai3fjolq.
- Minimum number of steps CodeForces - 805D(签到题)
- u-boot移植(八)---代码修改---存储控制器--MMU
- [cookie篇]cookie-parser之parser.js
- Linux给目录创建软链接的技巧
- python之类与对象(4)
- 【python】多个文件共用日志系统的重复打印问题
热门文章
- JavaScript初始
- 从零开始的全栈工程师——js篇2.10(对象与构造函数)
- 如何下载Oracle E-Business Suite (12.2.6) for Microsoft Windows x64 (64-bit)
- nmap -sT -A --script=smb-check-vulns -PO 172.16.21.170
- PHP代码规范的一些总结
- COGS 1944. 背驮式行走
- hdu-3549 Flow Problem---最大流模板题(dinic算法模板)
- 【51nod1815】调查任务(Tarjan+拓扑)
- 管道命令&#39;|&#39; 和xargs find命令找到后把所有找到的删除
- Spring学习记录(三)