hdu1010 Tempter of the Bone(深搜+剪枝问题)
2024-08-22 09:58:37
Tempter of the Bone Time Limit: / MS (Java/Others) Memory Limit: / K (Java/Others)
Total Submission(s): Accepted Submission(s): Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. 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 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. Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T ( < N, M < ; < T < ), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following: '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 's. This test case is not to be processed. Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. Sample Input S.X.
..X.
..XD
.... S.X.
..X.
...D Sample Output
NO
YES Author
ZHANG, Zheng Source
ZJCPC2004 Recommend
JGShining
#include <iostream>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int sx,sy,ex,ey;
int n,m;
int flag;
int d[][]={,,,,,-,-,};
char map[][];
void dfs(int x,int y,int t)
{
//cout<<x<<" "<<y<<" "<<t<<endl;
if(flag==)return;
if(t<sqrt(float((ex-x)*(ex-x)+(ey-y)*(ey-y)))||(t-abs(ex-x)+abs(ey-y))%)return;
else if(t==)
{
if(x==ex&&y==ey){flag=;return;}
else
return;
}
else
{
for(int i=;i<;i++)
{
int nx = x+d[i][];
int ny = y+d[i][];
if(nx>&&nx<=n&&ny>&&ny<=m&&(map[nx][ny]=='.'||map[nx][ny]=='D'))
{
map[nx][ny]='X';
dfs(nx,ny,t-);
map[nx][ny]='.';
}
}
}
return ;
}
int main()
{
int t,num;
char str[];
while(scanf("%d%d%d",&n,&m,&t),n||m||t)
{
num=;
for(int i=;i<=n;i++)
{
scanf("%s",str);
for(int j=;j<=m;j++)
{
map[i][j]=str[j-];
if(map[i][j]=='S')sx=i,sy=j;
else if(map[i][j]=='D')ex=i,ey=j,num++;
else if(map[i][j]=='.')num++;
}
} flag=;
if(num>=t)
dfs(sx,sy,t);
if(flag==)
printf("NO\n");
else
printf("YES\n");
}
return;
}
最新文章
- No.016:3Sum Closest
- 仓库、超市、服装、食品、批发零售手持打印PDA开单器-现场无线开单扫描 无线传输电脑
- python 代码片段20
- 澳洲最大的华资快递公司ACE 签约动软微信商城系统!
- 算法:求 Huffuman树 构造费用
- S3C6410嵌入式应用平台构建(三)
- 转:frame和iframe的区别
- Presto向分区表快速插入数据时出现&#39;target directory already exists&#39;的原因
- iOS 去掉小数点后边多余的0
- Uva - 177 - Paper Folding
- 页面缓存js问题解决
- Asteroids 爆破彗星
- 《Java大学教程》—第6章 类和对象
- Backbone.js学习之旅(一)
- 边框回归(Bounding Box Regression)详解
- 程序连接oracle数据库问题Cannot create PoolableConnectionFactory ...
- binlog开启和查看
- Java并发容器之非阻塞队列ConcurrentLinkedQueue
- 2017-2018-1 20155320第十周课下作业-IPC
- Windows + Ubuntu下JDK与adb/android环境变量配置完整教程