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

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1010奇偶剪枝  

2014-04-28 22:44:48|  分类: 搜索的入门 二分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

n可以把map看成这样:
n0 1 0 1 0 1
n1 0 1 0 1 0
n0 1 0 1 0 1
n1 0 1 0 1 0
n0 1 0 1 0 1
n从为 0 的格子走一步,必然走向为 1 的格子
n从为 1 的格子走一步,必然走向为 0 的格子
n即:
n 0 ->1或1->0 必然是奇数步
n 0->0 走1->1 必然是偶数步

结论:

所以当遇到从 0 走向 0 但是要求时间是奇数的,或者, 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达!





Tempter of the Bone

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



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   |   We have carefully selected several
similar problems for you:  1016 1241 1242 1072 1312 

 


Statistic | Submit | Discuss | Note






Home | TopHangzhou
Dianzi University Online Judge 3.0
Copyright ? 2005-2014 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang
Rongtao
 LinLe GaoJie GanLu
Total
0.004208(s) query 5, Server time : 2014-04-28 22:42:22, Gzip enabled

Administration

#include<iostream>/*这个真的特别的难啊*/
#include<cmath>
#include<stdlib.h>


using namespace std;
char map[9][9];
int start1,start2,end1,end2;
int n,m,t;
int wall;
int destination[4][2]={{0,-1},{0,1},{1,0},{-1,0}};/*方向的坐标啊*/
int escape;
void dfs(int startx,int starty,int time)
{
int i,times;
if(startx>n||starty>m||startx<=0||starty<=0) return ;
if(startx==end1&&starty==end2&&time==t) escape=1;
if(escape) return ;
times=t-time-abs(startx-end1)-abs(starty-end2);
if(times<0||times%2==1) return;
for(i=0;i<4;i++)/*深入进去查找我们的值,进行不断的回溯*/
{
if(map[startx+destination[i][0]][starty+destination[i][1]]!='X')/* 要走的话 这步必须的是我们的通的*/
{
map[startx+destination[i][0]][starty+destination[i][1]]='X';/* 要防止我们的发生过的,要标记*/
dfs(startx+destination[i][0],starty+destination[i][1],time+1); /*实间在 增加啊*/
map[startx+destination[i][0]][starty+destination[i][1]]='.';/*如果我们的这部递推下去之后,
(行的话,早就从escape 逃走了)不行了,责要把他还原为可出入的点*/
}
}
return ;
}
int main()
{
int i,j;
while(cin>>n>>m>>t)
{
if(n==0&&m==0&&t==0) break;
wall=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
start1=i;
start2=j;
}
else if(map[i][j]=='D')
{
end1=i;
end2=j;
}
else if(map[i][j]=='X')
{
wall++;/*墙的数量 进行排除我们的全部铺满的情况与实间的比值*/
}
}


}
if(n*m-wall<=t)
{
cout<<"NO"<<endl;
continue;
}
escape=0;
map[start1][start2]='X';/*进入之后就要把我们的后门堵死了瑟*/
dfs(start1,start2,0);
if(escape)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}


}
return 0;

}
/*
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
无论是从o 开始还是从1开始,
都是 0--->1 或者1--->0 都是奇数步
0-->0 , 1--->1 都是偶数步
*/



  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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