题解

一眼 bfs，但是有点不一样。

考虑使用 $2$ 个二进制位表示是否已经拿到钥匙和是否已经拯救小枫，扩展的时候写几个判断即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e3+13;
struct node{
    ll floor,x,y;
};
ll n,m,bx,by,ex,ey;
ll dist[4][MAXN][MAXN];
ll dire[2][4]={{1,-1,0,0},{0,0,1,-1}};
bool vis[4][MAXN][MAXN];
char ch[MAXN][MAXN];
queue<node> que;
inline void bfs(){
    node a,b;
    vis[0][bx][by]=true;
    que.push({0,bx,by});
    while(!que.empty()){
        a=que.front();
        que.pop();
        for(ll i=0;i<4;i++){
            b={a.floor,a.x+dire[0][i],a.y+dire[1][i]};
            if(b.x<=0||b.x>n||b.y<=0||b.y>m) continue;
            b.floor|=ch[b.x][b.y]=='!';//是否有钥匙
            b.floor|=(ch[b.x][b.y]=='M'&&(b.floor&1))<<1;//有钥匙且走到小枫位置可以解救
            if(ch[b.x][b.y]=='#'||vis[b.floor][b.x][b.y]) continue;
            if(ch[b.x][b.y]=='$'&&!(b.floor&2)) continue;
            dist[b.floor][b.x][b.y]=dist[a.floor][a.x][a.y]+1;
            vis[b.floor][b.x][b.y]=true;
            que.push(b);
        }
    }
    return;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>ch[i][j];
            if(ch[i][j]=='N'){
                bx=i;
                by=j;
            }
            else if(ch[i][j]=='@'){
                ex=i;
                ey=j;
            }
        }
    }
    bfs();
    if(vis[3][ex][ey]) cout<<"we were here together";
    else if(vis[0][ex][ey]) cout<<"sorry";
    else cout<<"NO";
    return 0;
}