ACM水問題−Rescue LK(AC,迷宮問題,DFS解)
Rescue LK
Time Limit:1000MS Memory Limit:65536K Total Submit:83 Accepted:42
Description
ziliang loves LK. But LK was kidnapped by Monster.oyy,and was put in a labyrinth. After thousands of hard fighting, ziliang finally enter the labyrinth. He must find a way to rescue LK !!! He has a map of the labyrinth, but the puzzle is too complicated, that he need your help.
Input
Input has several case. Each case first give an n and m, that is the height and length of the labyrinth. Followed by the map. In the map, ‘#’ means the wall, ‘Z’ means the position of ziliang, ‘L’ means position of LK. The ‘.’ Means empty cells. ziliang can only walk on empty cell,and can only go up,down,left,right. And n,m will be less than 50.
Output
If ziliang can reach LK, output “LK has a good life” Else output “Mission Failed”
Sample Input
Sample Output
Source
GDUT Monthly 2007.11 by ziliang
Time Limit:1000MS Memory Limit:65536K Total Submit:83 Accepted:42
Description
ziliang loves LK. But LK was kidnapped by Monster.oyy,and was put in a labyrinth. After thousands of hard fighting, ziliang finally enter the labyrinth. He must find a way to rescue LK !!! He has a map of the labyrinth, but the puzzle is too complicated, that he need your help.
Input
Input has several case. Each case first give an n and m, that is the height and length of the labyrinth. Followed by the map. In the map, ‘#’ means the wall, ‘Z’ means the position of ziliang, ‘L’ means position of LK. The ‘.’ Means empty cells. ziliang can only walk on empty cell,and can only go up,down,left,right. And n,m will be less than 50.
Output
If ziliang can reach LK, output “LK has a good life” Else output “Mission Failed”
Sample Input
5 5
#####
#Z..#
###.#
#..L#
#####
7 7
#######
#Z....#
#####.#
#####.#
#..#..#
#L.####
#######
Sample Output
LK has a good life
Mission Failed
Source
GDUT Monthly 2007.11 by ziliang
/* ------------------------------------------------------------------------------------------
： ， 、DFS ， ，
， DFS 。
： DFS 。 ， ， ，
。 1， ，
， 。
：AC，0MS
----------------------------------------------------------------------------------------*/
#include
char chMap[52][52] ;
const int nDir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}} ; //
int m = 0 ;
int n = 0 ;
int zX = 0 ; // X
int zY = 0 ; // Y
int DFS(int x,int y) ;
int main(void)
{
int i = 0 ;
int j = 0 ;
while(scanf("%d%d",&n,&m) != EOF)
{
getchar() ;
for(i = 0 ; i < n ; ++i)
{
for(j = 0 ; j < m ; ++j)
{
scanf("%c",&chMap[i][j]) ;
if('Z' == chMap[i][j])
{
zX = i ;
zY = j ;
}
}
getchar() ;
}
if(1 == DFS(zX,zY))
{
puts("LK has a good life") ;
}
else
{
puts("Mission Failed") ;
}
}
return 0 ;
}
int DFS(int x,int y)
{
int i = 0 ;
int j = 0 ;
if(x < 0 || y < 0 || x >= n || y >= m)
{
return 0 ;
}
for(i = 0 ; i < 4 ; ++i) //
{
if('L' == chMap[x+nDir[i][0]][y+nDir[i][1]])
{
return 1 ;
}
else if('.' == chMap[x+nDir[i][0]][y+nDir[i][1]])
{
chMap[x+nDir[i][0]][y+nDir[i][1]] = '#' ; // ，
if(1 == DFS(x+nDir[i][0],y+nDir[i][1])) //
{
return 1 ;
}
chMap[x+nDir[i][0]][y+nDir[i][1]] = '.' ; // 。
}
}
return 0 ;
}