[USACO11OPEN]Corn Maze S

题面翻译

奶牛们去一个 \(N\times M\) 玉米迷宫，\(2 \leq N \leq 300,2 \leq M \leq300\)。

迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。

如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。

玉米迷宫除了唯一的一个出口都被玉米包围。

迷宫中的每个元素都由以下项目中的一项组成：

玉米，# 表示，这些格子是不可以通过的。
草地，. 表示，可以简单的通过。
传送装置，每一对大写字母 \(\tt{A}\) 到 \(\tt{Z}\) 表示。
出口，= 表示。
起点， @ 表示

奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 \(1\) 个单位时间。从装置的一个结点到另一个结点不花时间。

输入格式

第一行：两个用空格隔开的整数 \(N\) 和 \(M\)。

第 \(2\sim N+1\) 行：第 \(i+1\) 行描述了迷宫中的第 \(i\) 行的情况（共有\(M\)个字符，每个字符中间没有空格）。

输出格式

一个整数，表示起点到出口所需的最短时间。

样例 #1

样例输入 #1

5 6
###=##
#.W.##
#.####
#.@W##
######

样例输出 #1

提示

例如以下矩阵，\(N=5,M=6\)。

###=##
#.W.##
#.####
#.@W##
######

唯一的一个装置的结点用大写字母 \(\tt{W}\) 表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费 \(0\) 个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了 \(3\) 个单位时间。

题解（bfs）

这一题其实就是一个广度优先遍历，但是这一题的坑点在于，他有一个传送门，我们要注意，传送门不需要记录通过多少次，我们只需要限制每个草地和起点经过一次就可以了，以防止死循环。
因为传送门有两个方向的请况，所以我们不能限制经过传送门的次数，但是这样并不会进入死循环，因为你走到这个传送门后，你之前走的草地都不能走了，所以并不会造成死循环。

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
#define pii pair<int, int>
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e4+10;
int _;
int n, m;
char mp[N][N], vis[N][N];
int xx1, yy1;
int ans = INT_MAX;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool check(int x, int y) {
    if(x < 1 || y < 1 || x > n || y > m) return false;
    return true;
}
struct node {
    int x, y, step;
};
pii f(int x, int y) {                       // 找到对应位置的传送门
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i == x && j == y) continue;
            if(mp[i][j] == mp[x][y]) return make_pair(i, j);
        }
    }
    return {0, 0};
}
void bfs() {
    queue<node> q;
    q.push({xx1, yy1, 0});
    vis[xx1][yy1] = 1;
    while(!q.empty()) {
        node tmp = q.front();
        q.pop();
        // cout << tmp.x << " " << tmp.y << " " << tmp.step << "\n";
        if(mp[tmp.x][tmp.y] == '=') {
            cout << tmp.step << "\n";
            return;
        }
        for(int i = 0; i < 4; i++) {
            int xx = tmp.x + dx[i];
            int yy = tmp.y + dy[i];
            if(check(xx, yy)) {
                if(mp[xx][yy] == '.' && vis[xx][yy] == 0) {
                    vis[xx][yy] = 1;
                    q.push({xx, yy, tmp.step+1});
                } else if(mp[xx][yy] >= 'A' && mp[xx][yy] <= 'Z') {
                    pii t = f(xx, yy);
                    q.push({t.fi, t.se, tmp.step+1});
                } else if(mp[xx][yy] == '=') {
                    vis[xx][yy] = 1;
                    q.push({xx, yy, tmp.step+1});
                }
            }
        }
    }
}
void solve() {
   cin >> n >> m;
   for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if(mp[i][j] == '@') {
                xx1 = i, yy1 = j;
            }
        }
    }
    bfs();
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    _ = 1;
    // cin >> _;
    while(_--) {
        solve();
    }
    return 0;
}