9도 oj-Temple of the bone
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.
입력:
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.
출력:
For each test case, print in one line "YES"if the doggie can survive, or "NO"otherwise.
샘플 입력:
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
샘플 출력:
NO
YES
문제 해결 방법:
dfs, 매번 검색 상태를 정확하게 찾아서 가지를 자르세요.
# include
# include
# include
char maze[100][100];
int n,m,t;
bool success;
int go[][2]={
-1,0,
1,0,
0,-1,
0,1
};
void dfs(int x, int y,int time)
{
int i=0;
for(i=0;i<4;i++)
{
int nx=x+go[i][0];
int ny=y+go[i][1];
if(nx<0||nx>=n||ny<0||ny>=m)
continue;
if(maze[nx][ny]=='X')
continue;
if(maze[nx][ny]=='D')
{
if(time+1==t)
{
success=true;
return;
}
else
continue;
}
//
maze[nx][ny]='X';
dfs(nx,ny,time+1);//
maze[nx][ny]='.';//
if(success==true)
return;
}
}
int main()
{
int i,j;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
if(n==0&&m==0&&t==0)
break;
//
memset(maze,0,sizeof(maze));
getchar();//
for(i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
이진 트리: 최저 공통 조상(LCA)Leetcode 문제 를 참조할 수 있습니다. 이진 트리가 주어지면 트리에서 주어진 두 노드의 lowest common ancestor(LCA)를 찾으십시오. 입력: root = [3,5,1,6,2,0,8,null,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.