Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 58766 Accepted Submission(s): 15983
Problem Description
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
'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
Sample Input
Sample Output
Author
Source
Recommend
#include <iostream>
#include <cstring>
using namespace std;
char maze[][];
int isw[][];
int dx[]={,,,-};
int dy[]={,,-,};
int N,M,T;
int curx,cury,endx,endy;
int abs(int n)
{
return n>=?n:-n;
}
int dfs(int curx,int cury,int curt) //判断从当前位置(curx,cury)能否用刚好curt时间到达结束点
{
if(curt==){ //当时间耗尽的时候,判断是否到达了结束点
if(curx==endx && cury==endy)
return ;
else
return ;
}
//剪枝 1 :奇偶剪枝
int m = abs(curx-endx) + abs(cury-endy); //理想情况下,开始点到终点的最小步数
int t = curt; //要求走t步正好走到终点
//当 t<m 时,一定不能到达
//当 t>=m 时,要用t步从开始点正好走到终点,分两部分。
// 一部分为最小步数 m ,另一部分是为了凑够t步而余外多走的几步,设为 a。
// 而走出去就一定要走回来,所以走出去的步数和回来的步数一定是相等的,为b步。
// a=2b,所以多走的a步一定是偶数。
// 这里的奇偶剪枝就是判断 a 是否为偶数。如果不是偶数,一定不能到达。
if( t<m || (t-m)& )
return ;
for(int i=;i<;i++){ //剪枝 2
if( <=curx+dx[i] && curx+dx[i]<=N && <=cury+dy[i] && cury+dy[i]<=M //如果没有越界
&& !isw[curx+dx[i]][cury+dy[i]] //如果下一步没有走过
&& maze[curx+dx[i]][cury+dy[i]]!='X' ){ //如果下一步不是墙
isw[curx+dx[i]][cury+dy[i]]=true;
if(dfs(curx+dx[i],cury+dy[i],curt-)) //如果下一步这样走可以生存,则返回1
return ;
isw[curx+dx[i]][cury+dy[i]]=false;
}
}
return ;
} int main()
{
while(cin>>N>>M>>T){
if(N== && M== && T==) break;
memset(isw,,sizeof(isw)); //将isw[][]数组初始化为false,表示还没有走过。
for(int i=;i<=N;i++)
for(int j=;j<=M;j++){
cin>>maze[i][j];
if(maze[i][j]=='S'){ //记录开始点的位置
curx=i;
cury=j;
}
else if(maze[i][j]=='D'){ //记录终点的位置
endx=i;
endy=j;
}
}
isw[curx][cury]=true; //开始位置赋true
if(dfs(curx,cury,T)) //如果能够生存,输出YES,否则输出NO
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return ;
}
Freecode : www.cnblogs.com/yym2013