bfs-献给阿尔吉侬的花束

题目来源

www.acwing.com/problem/content/1103/

题目

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

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

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

迷宫用一个 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.

输出样例：

1
2
3

5
1
oop!

AC代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;

const int MAX = 202;
char map[MAX][MAX]; //地图数组
int dis[MAX][MAX];  //距离数组
int max_x,max_y;    //x最大值，y最大值
int moving[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; //偏移量

bool isTrue(PII loc){
    //判断是否越界是否为墙
    return loc.x >= 0 && loc.x < max_x && loc.y >= 0 && loc.y <max_y && map[loc.x][loc.y] != '#';
}

//宽搜-bfs
//bfs算法类似于层次遍历算法，将遍历过的位置用数组记录，防止重复遍历
void bfs(PII start){
	map[start.x][start.y] = '#';    //先将起始位置设为已经访问
    queue<PII> q;                   //层次遍历需要用到数组
    q.push(start);                  //先将起始节点加入队列
    
    
    while(!q.empty()){
        PII now = q.front();        //取出队头，为当前所在节点
        PII next;                   //当前节点子节点
        q.pop();                    //将当前对头出队
       
        //遍历上下左右四个方向
        for(int i = 0; i < 4; i++){
            next.x = now.x + moving[i][0];
            next.y = now.y + moving[i][1];
            
            if(isTrue(next)){//判断子节点是否符合要求
                
                if(map[next.x][next.y] == '.'){
                    q.push(next);//符合要求就将子节点入队
                    dis[next.x][next.y] = dis[now.x][now.y] + 1;//记录子节点层次
                    map[next.x][next.y] = '#';//记录子节点已经访问
                }  
            	if(map[next.x][next.y] == 'E'){
            	    //如果子节点为出口则输出结果
                    cout<<dis[now.x][now.y]+1<<endl;
                    return;
                } 
            }
       }
    }
    cout<<"oop!"<<endl;
}
int main(){
    int n;
    cin>>n;
    int i = 0;
    while(n--){
        memset(map, '#', sizeof(map));
        memset(dis, 0, sizeof(dis));
        PII start;
        cin>>max_x>>max_y;
        for(int i = 0; i < max_x; i++)
            cin>>map[i];
        for(int i = 0; i < max_x; i++){
            for(int j = 0; j < max_y; j++){
                if(map[i][j] == 'S'){
                    start.x = i;
                    start.y = j;
                }
            }
        }
        bfs(start);
    }
    return 0;
}