题目描述

迷宫问题：设置起点和终点，路径上有障碍，问起点到达终点的最短距离，若不存在最短距离，则输出-1

算法1

(bfs)

找到起点，把相邻的点（上下左右）加入队列，更新这些点到起点的最短距离，最终遍历到终点，输出距离，若遍历不到终点，则输出-1

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second 
using namespace std;
char g[210][210];
int dist[210][210];
typedef pair<int, int >PII;
int n, m;
int bfs(PII start,PII end)  //不存在递归
{
    queue<PII> q;
    memset(dist,-1,sizeof dist);  //初始化为-1，表示为没有经过
    dist[start.x][start.y] = 0;   //自己到自己的距离为0
    q.push(start);  
    int dx[] = { -1,0,1, 0 };
    int dy[] = { 0,1,0,-1 };
    while (q.size()) {   //q不为空
        auto t = q.front();  //取出队首
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n ||y<0 ||y>=m ) {  //出界
                continue;
            }if (g[x][y] == '#') {   //不可走
                continue;
            }
            if (dist[x][y] != -1) {  //已经走过
                continue;
            }
            dist[x][y] = dist[t.x][t.y] + 1; //队首距离家加1
            if (end == make_pair(x, y)) return dist[x][y];  //如果pair数组（x,y）等于end，说明最短距离已经找到了
            q.push({x,y});  //加入队列
        }
    }
    return -1; //未找到，返回-1
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; i++) scanf("%s", g[i]);
        PII start, end;
        for (int i = 0; i < n; i++) {  //找到start点和end点
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'S') {
                    start = { i,j };
                }
                else if (g[i][j] == 'E') {
                    end = { i,j };
                }
            }
        }
        int distance = bfs(start,end);  //求最短距离
        if (distance == -1) {
            printf("oop!\n");
        }
        else {
            printf("%d\n",distance);
        }

    }

    return 0;
}

注意如果从g[1][1] 开始读取,注意输入的合法性

 for (int i = 1; i <= n; i++)
{
    char c = getchar();
    for (int j = 1; j <= m; j++) {
        scanf("%c", &g[i][j]);
    }

}
或者用cin