Day - 25 獻給阿爾吉侬的花束（BFS）

AcWing 1101.獻給阿爾吉侬的花束

BFS應用——走迷宮

考點：BFS

阿爾吉侬是一隻聰明又慵懶的小白鼠，它最擅長的就是走各種各樣的迷宮。

今天它要挑戰一個非常大的迷宮，研究員們為了鼓勵阿爾吉侬盡快到達終點，就在終點放了一塊阿爾吉侬最喜歡的奶酪。

現在研究員們想知道，如果阿爾吉侬足夠聰明，它最少需要多少時間就能吃到奶酪。

迷宮用一個 R×CR×C 的字元矩陣來表示。

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

阿爾吉侬在 1 個機關時間内可以從目前的位置走到它上下左右四個方向上的任意一個位置，但不能走出地圖邊界。

輸入格式

第一行是一個正整數 TT，表示一共有 TT 組資料。

每一組資料的第一行包含了兩個用空格分開的正整數 RR 和 CC，表示地圖是一個 R×CR×C 的矩陣。

接下來的 RR 行描述了地圖的具體内容，每一行包含了 CC 個字元。字元含義如題目描述中所述。保證有且僅有一個 S 和 E。

輸出格式

對于每一組資料，輸出阿爾吉侬吃到奶酪的最少機關時間。

若阿爾吉侬無法吃到奶酪，則輸出“oop!”（隻輸出引号裡面的内容，不輸出引号）。

每組資料的輸出結果占一行。

資料範圍

1<T≤101<T≤10,

2≤R,C≤2002≤R,C≤200

輸入樣例：

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

輸出樣例：

5
1
oop!
           

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

using namespace std;

const int N = 210;

int R,C;
char str[N][N];
int dist[N][N];
typedef pair<int,int> PII;

int bfs(PII start,PII end)
{
    queue<PII> q;
    q.push(start);
    memset(dist,-1,sizeof dist);
    dist[start.first][start.second] = 0;
    
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a >= 0 && a < R && b >= 0 && b < C && str[a][b] != '#' && dist[a][b] == -1)
                dist[a][b] = dist[t.first][t.second] + 1;
            else continue;
            
            if(end == make_pair(a,b)) return dist[a][b];
            
            q.push({a,b});
        }
        
    }
    return -1;
    
}
int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        cin >> R >> C;
        for(int i = 0; i < R; i ++ )
            for(int j = 0; j < C; j ++ )
                cin >> str[i][j];
        
       PII start,end;
       
       for(int i = 0; i < R; i ++ )
        for(int j = 0; j < C; j ++ )
        {
            if(str[i][j] == 'S') start = {i,j};
            if(str[i][j] == 'E') end = {i,j};
        }
        
        int distance = bfs(start,end);
        if(bfs(start,end) == -1) cout << "oop!" << endl;
        else
        cout << distance << endl;
    }
    
    return 0;
    
}