欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

暑假训练 迷宫寻宝(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找出最短路径。。。

相关标签: bfs与dfs