洛谷 P1825 【[USACO11OPEN]玉米田迷宫Corn Maze】

P1825

传送门

简单的题意

就是一个有传送门的迷宫问题（我一开始以为是只有1个传送门，然后我就凉了）.

大体思路

先把传送门先存起来，然后跑一下\(BFS\)。

然后，就做完了.

代码鸭

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#define A 305

using namespace std;
int ans, n, m, map[A][A], lu[400010][4];
int u[5] = {0, 0, 0, -1, 1}, v[5] = {0, -1, 1, 0, 0};
int dx, dy, sx, sy;
struct node {
    int x, y;
    bool s;
} w1[27], w2[27];

void bfs() {
    int head = 0, tail = 1;
    lu[tail][1] = sx, lu[tail][2] = sy, lu[tail][3] = 1;
    map[sx][sy] = 1;
    while(head < tail) {
        head++;
        for(int i = 1; i <= 4; i++) {
            int x = lu[head][1] + u[i], y = lu[head][2] + v[i];
            //if(w1.x == x && w1.y == y) x = w2.x, y = w2.y;
            //if(w2.x == x && w2.y == y) x = w1.x, y = w1.y;
            for(int i = 1; i <= 26; i++)
                if(x == w1[i].x && y == w1[i].y) {
                    x = w2[i].x, y = w2[i].y;
                    break;
                } else if(x == w2[i].x && y == w2[i].y) {
                    x = w1[i].x, y = w1[i].y;
                    break;
                }
            if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == 0) {
                tail++;
                map[x][y] = 1;
                lu[tail][1] = x, lu[tail][2] = y, lu[tail][3] = lu[head][3] + 1;
                if(x == dx && y == dy) {
                    ans = lu[tail][3];
                    head = tail;
                    break;
                }
            }
        }
    }
}


int main() {
    char s;
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin>>s;
            if (s == '=') dx = i, dy = j, map[i][j] = 0;
            if (s == '@') sx = i, sy = j, map[i][j] = 0;
            if (s == '#') map[i][j] = 1;
            if (s == '.') map[i][j] = 0;
            if (s >= 'A' && s <= 'Z') {
                map[i][j] = 0;
                if (w1[s - 'A' + 1].s == 0) w1[s - 'A' + 1].s = 1, w1[s - 'A' + 1].x = i, w1[s - 'A' + 1].y = j;
                else w2[s - 'A' + 1].s = 1, w2[s - 'A' + 1].x = i, w2[s - 'A' + 1].y = j;
            }
        }
    bfs();
    cout<<ans - 1;
}