暑假训练 迷宫寻宝(bfs)
程序员文章站
2022-05-23 19:45:59
...
题目描述
洪尼玛今天准备去寻宝,在一个n*n (n行, n列)的迷宫中,存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的,即在迷宫中的一个位置,只能走到与它直接相邻的其他四个位置(上、下、左、右)。现洪尼玛在迷宫的入口处,问他最少需要走几步才能拿到宝藏?若永远无法拿到宝藏,则输出-1。
Input
多组测试数据。
每组数据输入第一行为正整数n,表示迷宫大小。
接下来n行,每行包括n个字符,其中字符’.’表示该位置为空地,字符’#’表示该位置为墙壁,字符’S’表示该位置为入口,字符’E’表示该位置为宝藏,输入数据中只有这四种字符,并且’S’和’E’仅出现一次。
n≤1000
Output
输出拿到宝藏最少需要走的步数,若永远无法拿到宝藏,则输出-1。
Sample Input
5
S.#..
#.#.#
#.#.#
#…E
#….
Sample Output
7
代码如下:
#include<cstdio>
#include<queue>
using namespace std;
int run[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,e1,e2,y=0,pop,ptp=0,by=0;
queue<int>q1;
queue<int>q2;
char ma;
int intmap[1010][1010];
void bfs(){
while(!q1.empty() && y == 0){
e1 = q1.front();
e2 = q2.front();
pop = intmap[e1][e2];
for(int i = 0; i < 4; i++){
e1 = q1.front() + run[i][0];
e2 = q2.front() + run[i][1];
if(1 <= e1 && e1 <= n && 1 <= e2 && e2 <= n){
if(intmap[e1][e2] == 0){
q1.push(e1);
q2.push(e2);
intmap[e1][e2] = pop+1;
}
else if(intmap[e1][e2] == -2){
ptp = pop + 1;
y = 1;
}
}
}
q1.pop();
q2.pop();
}
}
int main()
{
while(~scanf("%d", &n)){
y=0; by=0; ptp=-1;
for(int i = 1; i <= n; i++)
{
scanf("%c", &ma);
for(int j = 1; j <= n; j++)
{
scanf("%c", &ma);
switch(ma)
{
case'.':intmap[i][j] = 0;break;
case'#':intmap[i][j] = 1;break;
case'S':intmap[i][j] = 0; q1.push(i); q2.push(j); break;
case'E':intmap[i][j] = -2;break;
}
}
}
bfs();
printf("%d\n", ptp);
while(!q1.empty()){
q1.pop();
q2.pop();
}
}
return 0;
}
bfs找出最短路径。。。