Hust oj 1949 寻找宝藏（BFS）_综合

寻找宝藏

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 166(73 users)

Total Accepted: 90(72 users)

Rating:

Special Judge: No

Description

在一个地图中，* 表示起点， $ 表示宝藏的藏匿地点， # 表示墙，+ 表示通道，问能否找到宝藏。

Input

多组测试数据：

对于每组数据：第一行两个整数N, M。 (N,M<=20)

接下来是一个N x M 的地图。

Output

若能找到宝藏输出“RedHat V5!” 否则输出“Orz!”。每组输出数据占一行。

Sample Input

7 10
+++++++++*
+#########
++++++++++
#########+
++++++++++
+#########

+++++++++$

8 8
$#######
#++++++#
#++++++#
#++++++#
#++++++#
#++++++#
######+#
++++++*+

Sample Output

RedHat V5!

Orz!

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;const int Maxn = 25;
int vis[Maxn][Maxn];
char Map[Maxn][Maxn];
int fx[4] = {0,0,1,-1};
int fy[4] = {1,-1,0,0};
struct Point
{int x;int y;int step;
};
int n,m;
int bfs(int x1,int y1,int x2,int y2)
{memset(vis,0,sizeof(vis));Point Start,End,Temp;queue<Point>q;vis[x1][y1] = 1;Start.x = x1;Start.y = y1;Start.step = 0;q.push(Start);while(!q.empty()){Temp = q.front();if(Temp.x == x2 && Temp .y == y2){return Temp.step;break;}q.pop();for(int i=0;i<4;i++){End.x = fx[i] + Temp.x;End.y = fy[i] + Temp.y;if(End.x >= 0 && End.x <= n && End.y >= 0 && End.y <= m && !vis[End.x][End.y] && Map[End.x][End.y] != '#'){End.step = Temp.step + 1;vis[End.x][End.y] = 1;q.push(End);}}}return -1;
}int main()
{int x1,x2,y1,y2;while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++){getchar();for(int j=0;j<m;j++){scanf("%c",&Map[i][j]);if(Map[i][j] == '*'){x1 = i;y1 = j;}if(Map[i][j] == '$'){x2 = i;y2 = j;}}}int ans = bfs(x1,y1,x2,y2);if(ans != -1)printf("RedHat V5!\n");elseprintf("Orz!\n");}
}