广度优先搜索|T9 正经题解(

由于要存储多种状态，这里使用三维数组vis[N][N][3]存储每一位的访问情况和状态
废话多说（），上代码（代码解释已经在代码中注释）

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1003;
char a[N][N];
bool vis[N][N][3]; // "[3]": 状态: 0=无钥匙, 1=有钥匙,没有救出小枫, 2=救出小枫
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int sx,sy,ex,ey,mx,my,kx,ky; // sx,sy:起点位置, ex,ey:终点位置, mx,my:小枫位置, kx,ky:钥匙位置
bool onlyNoon;
struct Pos{
    int x,y,state; // state:0,1,2
};
bool check(int x,int y){
    return (1 <= x && x <= n && 1 <= y && y <= m);
}
signed main(){
    cin>>n>>m;
    for(auto i=1;i<=n;i++) for(auto j=1;j<=m;j++) cin>>a[i][j];
    for(auto i=1;i<=n;i++) for(auto j=1;j<=m;j++){
        if(a[i][j] == 'N'){
            vis[i][j][0] = true;
            sx = i;
            sy = j;
        }
        if(a[i][j] == 'M'){
            mx = i;
            my = j;
        }
        if(a[i][j] == '!'){
            kx = i;
            ky = j;
        }
        if(a[i][j] == '@'){
            ex = i;
            ey = j;
        }
    }
    queue<Pos> q;
    q.push({sx,sy,0});
    onlyNoon = false;
    while(q.size()){ // 等同于while(!q.empty()) 
        Pos now=q.front();
        q.pop();
        if(now.x == ex && now.y == ey){
            if(now.state == 2){ // 如果走到终点并且满足要求
                cout<<"we were here together";
                return 0;
            }else onlyNoon=true; // 标记
        }
        for(auto i=0;i<4;i++){
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(check(nx,ny) && a[nx][ny] != '#'){
                int nstate = now.state;
                if(a[nx][ny] == '!' && nstate == 0) nstate = 1; // 拿到钥匙
                if(a[nx][ny] == 'M' && nstate == 1) nstate = 2; // 解救小枫
                if(a[nx][ny] == '$' && nstate != 2) continue; // state != 2 无法通过
                if(!vis[nx][ny][nstate]){
                    vis[nx][ny][nstate] = true;
                    q.push({nx,ny,nstate});
                }
            }
        }
    }
    cout<<(onlyNoon ? "sorry" : "NO");
    return 0;
}

时间复杂度: $O(n \times m)$
空间复杂度: $O(n \times m)$
预计得分: 管你多少反正能AC（