hdu 1010
4000 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1010
Tempter of the Bone
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：89573 Acceepted Submission(s)：24362
Problem Description
The doggie found a bone in ancint maze、which fascinated hia lot.However、when he picked it up、the maze began to shak、and the doggie could feel the ground sinking.He realized ththe boina
The maze was a rectangle with sizs N by M.The e e was a door in the maze.At the begining、the door was closed and it would Onet the T T-th second fora Shotperiod of time（less than 1 second）.The thethererererereggt the the the the thethethethethethethethe thethethethethethe eeeeeeeerererererererererereaaaaattttttttttttttttttttttttttttttttttttttttttttttof the up per，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 aton block for mone sed，nor could the move？Please help him.
Input
The input consists of multile test cases.The first line of each test case contains three integers N，M，and T(1'X'：a block of wall，which the doggie cannot enter；
'S':the start point of the doggie;
'D'：the Doror
'::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”others wise.
Sample Input
Sample Output
犬がいます。迷路の中に骨があります。この犬は食いしん坊で、迷宮に入って骨をくわえて歩きました。骨をくわえて歩く時、彼は一歩歩くごとに穴に落ち始めました。犬は一歩歩くごとに1秒で上下左右に歩くことができます。しかし、「X」は壁を表しています。
Tempter of the Bone
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：89573 Acceepted Submission(s)：24362
Problem Description
The doggie found a bone in ancint maze、which fascinated hia lot.However、when he picked it up、the maze began to shak、and the doggie could feel the ground sinking.He realized ththe boina
The maze was a rectangle with sizs N by M.The e e was a door in the maze.At the begining、the door was closed and it would Onet the T T-th second fora Shotperiod of time（less than 1 second）.The thethererererereggt the the the the thethethethethethethethe thethethethethethe eeeeeeeerererererererererereaaaaattttttttttttttttttttttttttttttttttttttttttttttof the up per，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 aton block for mone sed，nor could the move？Please help him.
Input
The input consists of multile test cases.The first line of each test case contains three integers N，M，and T(1
'S':the start point of the doggie;
'D'：the Doror
'::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”others wise.
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
犬がいます。迷路の中に骨があります。この犬は食いしん坊で、迷宮に入って骨をくわえて歩きました。骨をくわえて歩く時、彼は一歩歩くごとに穴に落ち始めました。犬は一歩歩くごとに1秒で上下左右に歩くことができます。しかし、「X」は壁を表しています。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
int sx,sy,gx,gy;
int T,t,flag;
char map[10][10];
int N,M;
int d[4][2]= { {1,0},{0,1},{0,-1},{-1,0} };
void bfs(int x,int y,int t)
{
if(flag==1)
return;
if(t<abs(x-gx)-abs(y-gy)||(t-abs(x-gx)-abs(y-gy))%2==1)
return;
if(t==0)
{
if(x==gx&&y==gy)
{
flag=1;
return;
}
else
return;
}
for(int i=0; i<4; i++)
{
int nx=d[i][0]+x;
int ny=d[i][1]+y;
if(nx>=0&&ny>=0&&nx<N&&ny<M&&(map[nx][ny]=='.'||map[nx][ny]=='D'))
{
map[nx][ny]='X';
bfs(nx,ny,t-1);
map[nx][ny]='.';
}
}
return;
}
int main()
{
while(~scanf("%d%d%d",&N,&M,&T))
{
if(N==0&&M==0&&T==0)
break;
for(int i=0; i<N; i++)
{
scanf("%s",map[i]);
for(int j=0; j<M; j++)
{
if(map[i][j]=='S')
{
sx=i,sy=j;
}
if(map[i][j]=='D')
{
gx=i,gy=j;
}
}
}
flag=0;
t=T;
bfs(sx,sy,t);
if(flag)
printf("YES
");
else
printf("NO
");
}
//cout << "Hello world!" << endl;
return 0;
}