献给阿尔吉侬的花束

算法标签：BFS

来源： 《信息学奥赛一本通》

题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式

第一行是一个正整数 T，表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R 和 C，表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式

对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围

1<T≤10,
2≤R,C≤200

输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

思路

bfs找最短路径

bfs

利用队列，进行层序遍历，能找到最短路径.

框架
取出队头元素，将该元素的扩展元素放置队尾.

queue 初始状态
while(queue非空)
    {
        t<-队头
        for(扩展t)
            {
                新节点
                if(判断条件)
                    {
                        新节点添加到队尾
                    }
            }

    }

简单的示意图

C++ 代码

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;//用来储存横纵坐标

const int N=220;
int r,c;

char g[N][N];//地图
int dist[N][N];//距离加判断真伪

int bfs(PII sta,PII end)//宽搜 找最短路径
{
    queue<PII>q;
    memset(dist,-1,sizeof dist);//dist默认-1用来特判，起到bool作用
    dist[sta.x][sta.y]=0;//起点初始化
    q.push(sta);

    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//当前一个点可能到达的4个点的偏移量
    while(q.size())
        {
            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||y<0||x>=r||y>=c)continue;//边界
                    else if(dist[x][y]!=-1)continue;//走过
                    else if(g[x][y]=='#')continue;//墙

                    dist[x][y]=dist[t.x][t.y]+1;//当前点到起始位置的距离更新
                    if(end==make_pair(x,y))return dist[x][y];
                    q.push({x,y});//满足条件则插入队末
                }
        }
    return -1;//没找到就返回-1
}
int main()
{
    int t;
    cin>>t;

    while(t--)
        {
            cin>>r>>c;
            for(int i=0;i<r;i++)cin>>g[i];//用S读完一行

            PII sta,end;
            for(int i=0;i<r;i++)
                for(int j=0;j<c;j++)
                    if(g[i][j]=='S')sta={i,j};//开始点
                    else if(g[i][j]=='E')end={i,j};//结束点


            if(bfs(sta,end)==-1)cout<<"oop!"<<endl;
            else cout<<bfs(sta,end)<<endl;
        }
    return 0;
}