题解：AT_abc420_d [ABC420D] Toggle Maze

Hughpig · 2023-10-02 18:39:43 · 题解

使用广度优先搜索解决此题。与一般的 BFS 不同，经过 ? 点会改变某些点是否可以通过。

考虑一扇门是否开启仅与走到 ? 点的次数的奇偶性相关，因此我们可以在搜索的状态中记录一个变量 open 表示当前是否让本来关着的门打开，本来打开的门关上。

但是直接搜索会 TLE，比如会在某个点重复的经过，可以记录一个 map<pair<pair<int,int>,bool>> vis 表示某个状态是否被访问过。如果已经访问过那么之前就已经搜索过了这个状态，就不用继续搜索了。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define up(l,r,i) for(int i=(l);(i)<=(r);++i)
#define pii pair<ll,ll>

constexpr int N=509;

ll n,m,sx,sy,ex,ey;
char a[N][N];

map<pair<pii,bool>,bool> vis;

struct node{
    ll x,y,step;
    bool open;
};

void bfs(){
    queue<node> q;
    q.push({sx,sy,0,0});
    while(!q.empty()){
        node tmp=q.front();q.pop();
        if(vis[{ {tmp.x,tmp.y},tmp.open}])continue;
        vis[{ {tmp.x,tmp.y},tmp.open}]=1;
        if(tmp.x==ex&&tmp.y==ey){
            cout<<tmp.step<<"\n";
            return;
        }
        up(-1,1,i){
            up(-1,1,j){
                if(abs(i)+abs(j)!=1)continue;
                ll tx=tmp.x+i,ty=tmp.y+j;
                if(tx<1||tx>n||ty<1||ty>m)continue;
                if(a[tx][ty]=='#')continue;
                if(a[tx][ty]=='.'||a[tx][ty]=='G'||a[tx][ty]=='S'){
                    q.push({tx,ty,tmp.step+1,tmp.open});
                }
                else if(a[tx][ty]=='?'){
                    q.push({tx,ty,tmp.step+1,!tmp.open});
                }
                else if(a[tx][ty]=='o'&&tmp.open==0){
                    q.push({tx,ty,tmp.step+1,tmp.open});
                }
                else if(a[tx][ty]=='x'&&tmp.open==1){
                    q.push({tx,ty,tmp.step+1,tmp.open});
                }
            }
        }
    }
    cout<<"-1\n";
}

int main()
{
    cin>>n>>m;
    up(1,n,i){
        up(1,m,j){
               cin>>a[i][j];
               if(a[i][j]=='S')sx=i,sy=j;
               if(a[i][j]=='G')ex=i,ey=j;
        }
    }
    bfs();
    return 0;
}

::::