两个BFS搞定

思路：先解决小午能否救出小枫。

若无法救出则：
A.小午能独自到达终点，输出"sorry"
B.小午不能独自到达终点，输出“NO”

若能救出：则判断小午和小枫能否一起到达终点：
A.能一起到达终点，输出“we were here together”
B.不能一起到达终点，输出“NO”

---

以下是代码实现：

#include<iostream>
#include<queue>
#include<cstring>//用于重置 vis记录
using namespace std;//头文件&命名空间

int n,m;
int sx,sy,fx,fy,px,py,kx,ky;//s:起点 f:终点 p:小枫 k:钥匙
char mp[1010][1010];
bool vis[1010][1010];

void BFS_save_feng(){      //先解决小午能否救出小枫。
    queue<pair<int,int>>q;
    q.push({sx,sy});
    vis[sx][sy]=1;

    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();

        int dx[4]{-1,1,0,0};
        int dy[4]{0,0,1,-1};

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];

            if(nx>=0&&nx<n&&ny>=0&&ny<m&&vis[nx][ny]==0&&mp[nx][ny]!='$'&&mp[nx][ny]!='#'){
                q.push({nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return;
}

void BFS_get_out(){       //若能救出：则判断小午和小枫能否一起到达终点
    queue<pair<int,int>>q;
    q.push({sx,sy});
    vis[sx][sy]=1;

    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();

        int dx[4]{-1,1,0,0};
        int dy[4]{0,0,1,-1};

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];

            if(nx>=0&&nx<n&&ny>=0&&ny<m&&vis[nx][ny]==0&&mp[nx][ny]!='#'){ //在主函数中将所有的高墙、钥匙                                                                                                                      
                q.push({nx,ny});                                           //以及小枫的位置改成通路方便判断
                vis[nx][ny]=1;
            }
        }
    }
    return;
}
int main(){
    
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='N'){
                sx=i,sy=j;
            }
            if(mp[i][j]=='M'){
                px=i,py=j;
            }
            if(mp[i][j]=='!'){
                kx=i,ky=j;
            }
            if(mp[i][j]=='@'){
                fx=i,fy=j;
            }                  //添加特殊点位坐标
        }
    }

    BFS_save_feng();//解决小午能否救出小枫

    if((vis[px][py]==0||vis[kx][ky]==0)&&vis[fx][fy]==0){  //若无法救出则：A.小午能独自到达终点，输出"sorry"
        cout<<"NO";
        return 0;
    }
    else if((vis[px][py]==0||vis[kx][ky]==0)&&vis[fx][fy]==1){ //B.小午不能独自到达终点，输出“NO”
        cout<<"sorry";
        return 0;
    }
    else{                                    //若能救出：
        for(int i=0;i<n;i++){               //(在那之前先把vis初始化、将钥匙、小枫位置以及高墙变为可通行的道路)
            for(int j=0;j<m;j++){
                if(mp[i][j]=='!'||mp[i][j]=='$'||mp[i][j]=='M'){
                    mp[i][j]='.';
                }
            }
        }
    }

    memset(vis,0,sizeof(vis));

    BFS_get_out();  //则判断小午和小枫能否一起到达终点：

    if(vis[fx][fy]==1)cout<<"we were here together";  //A.能一起到达终点，输出“we were here together”
    else cout<<"NO";                                  //B.不能一起到达终点，输出“NO”
    return 0;
}

---

然后就这么结束了