注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1010 Tempter of the Bone  

2012-08-03 16:39:42|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是一题很经典的DFS,老师讲课的时候就是拿着题作为例题的。
先放题目:

Tempter of the Bone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 37761    Accepted Submission(s): 10199


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 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.
 

Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), 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 0'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
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
 

Sample Output
NO YES
 

Author
ZHANG, Zheng
 

Source
 

Recommend
JGShining
 


这题需要注意的是要剪枝,不然会超时。
题目意思就是狗从S开始,能不能正好在T秒是到D,”.“是可以走的,“X”是墙。
接下来就是剪枝
第一个剪枝我们可以想到,当剩下的步数大于剩下的时间的时候,狗是不能走到的;

接下来我们来第二个剪枝:
我们把map的奇偶性以01编号:
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
我们发现从0走一步一定走到1,从1走一步一定走到0。
也就是说,如果当前的狗所在的坐标与D的坐标奇偶性不一样,那么狗需要走奇数步。
同理,如果狗所在坐标与D的坐标奇偶性一样,那么狗需要走偶数步数。

也就是说,狗的坐标x、y和对2取余是它的奇偶性,Dxy和对2取余是D的奇偶性。
两个奇偶性一加再对2取余,拿这个余数去与剩下时间对2取余的余数作比较即可。

可想而知,这里又摘掉了非常多的树枝。

下面是代码:


#include<iostream>
#include <stdlib.h>
using namespace std;
bool escape;
int temp;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
char map[10][10];
int m,n,T;
int si,sj,xi,xj,di,dj;


void dfs(int si,int sj,int cnt)
{
int i;
if(si > n || sj > m || si <= 0 || sj <= 0) return;
if(si == di && sj == dj && cnt == T) escape = 1;
if(escape) return;

temp = T - cnt - abs(si - di) - abs(sj - dj);
if(temp < 0 || temp & 1) return;

for(i = 0;i < 4;i ++)
{
if(map[si + dir[i][0]][sj + dir[i][1]] != 'X')
{
map[si + dir[i][0]][sj + dir[i][1]] = 'X';
dfs(si + dir[i][0],sj + dir[i][1],cnt + 1);
map[si + dir[i][0]][sj + dir[i][1]] = '.';
}
}
return;
}



int main()
{
int wall;
while(~scanf("%d %d %d",&n,&m,&T))
{
if(n == 0 && n == 0 && T == 0) break;
wall = 0;
int i,j;
for(i = 1;i <= n ;i ++)
{
for(j = 1;j <=m;j ++)
{
cin>>map[i][j];
if(map[i][j] == 'S')
{
si = i;
sj = j;
}
if(map[i][j] == 'X') wall++;

if(map[i][j] == 'D')
{
di = i;
dj = j;
}
}
}

if(m * n - wall <= T)
{
cout<<"NO"<<endl;
continue;
}
escape = 0;
map[si][sj] = 'X';
dfs(si,sj,0);

if(escape)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;

}
return 0;
}





  评论这张
 
阅读(209)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018