[USACO11OPEN]玉米田迷宫Corn Maze

忘是亡心i 2021-11-13 15:12 250阅读 0赞

[题面][Link 1]

bfs

注意事项

### ①鬼畜死循环TLE ###

### ②装置不成对 ###

### ③本来最优解被传送门的\#给盖住了，必须新开一个数组来存 ###

### ④步数没有+对，因为遇到传送门是跳着走的 ###

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include<map>
    using namespace std;
    int n,m;
    char a[302][302];
    char usual[302][302];
    char special[302][302];
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    struct qwq {
        int my_x1,my_x2,my_y1,my_y2;
        int flag;
    };
    map<char,qwq> cs;
    int be_x,be_y;struct Pos {
        int x,y,step;
    };
    queue<Pos> bfs;
    int main() {
        cin>>n>>m;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cin>>a[i][j];
                special[i][j]=a[i][j];
                usual[i][j]=a[i][j];
                if(a[i][j]>='A'&&a[i][j]<='Z') {
                    if(cs[a[i][j]].flag==0) {
                        cs[a[i][j]].my_x1=i;
                        cs[a[i][j]].my_y1=j;
                        cs[a[i][j]].flag++;
                    } else {
                        cs[a[i][j]].my_x2=i;
                        cs[a[i][j]].my_y2=j;
                        cs[a[i][j]].flag++;
                    }
                    special[i][j]=a[i][j];
                } else if(a[i][j]=='@') {
                    be_x=i;
                    be_y=j;
                }
            }
        }
        bfs.push({be_x,be_y,0});
    
        while(!bfs.empty()) {
            Pos head = bfs.front();
            for(int i = 0; i < 4; i++) {
                int tx = head.x+dx[i], ty = head.y+dy[i];
                if(a[tx][ty]=='=') {
                    cout<<head.step+1<<endl;
                    return 0;
                } else if(a[tx][ty]>='A'&&a[tx][ty]<='Z' && special[tx][ty]!='#' ) {
                    if(cs[a[tx][ty]].flag==1) {
                        special[tx][ty]='#';
                        bfs.push({tx,ty,head.step+1});
                        continue;
                    }
                    special[tx][ty]='#';
                    char flag2=a[tx][ty];
                    if(cs[flag2].my_x1==tx && cs[flag2].my_y1 == ty) {
                        tx=cs[flag2].my_x2;
                        ty=cs[flag2].my_y2;
                    } else {
                        tx=cs[flag2].my_x1;
                        ty=cs[flag2].my_y1;
                    }
                    bfs.push({tx,ty,head.step+1});
                } else if(a[tx][ty]=='.' && usual[tx][ty]=='.') {
                    usual[tx][ty]='#';
                    bfs.push({tx,ty,head.step+1});
                }
            }
            bfs.pop();
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ainiyuling/p/11188478.html

[Link 1]: https://www.luogu.org/problemnew/show/P1825