BFS

这个bfs稍微复杂一点，两遍bfs即可，一个是去判断小午能否拿到钥匙解救小枫，并且能不能出迷宫，第二个，小枫能不能出迷宫，通过判断即可！

/*
 *  @filename:~/Documents/workspace/vscode_space
 *  @author: Ly_boy
 *  @date: 2025-05-15 14:22:17  星期四
 *  @compiler: 2025 by Ly_boy, All Rights Reserved.
 */
#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

char mp[1005][1005];
int n, m, nx, ny, mx, my, yaoshix, yaoshiy;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool vis[1005][1005];
bool Ntoyaoshi = false;
bool YaoshiToM = false;
bool Mtochukou = false;
bool Ntochukou = false;
queue<pair<int, int>> q;

void bfs(int sx, int sy) // 小午的遍历，看能否找到钥匙、小枫，出口
{
    memset(vis, false, sizeof(vis));
    q.push({sx, sy});
    vis[sx][sy] = true;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        if (mp[x][y] == '!') // 找到钥匙
            Ntoyaoshi = true;
        if (mp[x][y] == 'M') // 找到小枫
            YaoshiToM = true;
        if (mp[x][y] == '@') // 找到出口
            Ntochukou = true;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i];
            int newy = y + dy[i];
            if (newx >= 1 && newx <= n && newy >= 1 && newy <= m && mp[newx][newy] != '#' && mp[newx][newy] != '$' && !vis[newx][newy])
            {
                vis[newx][newy] = true;
                q.push({newx, newy});
            }
        }
    }
}

void bfs2(int sx, int sy) // 小枫找到出口
{
    memset(vis, false, sizeof(vis));
    q.push({sx, sy});
    vis[sx][sy] = true;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        if (mp[x][y] == '@')
        {
            Mtochukou = true;
            return;
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i];
            int newy = y + dy[i];
            if (newx >= 1 && newx <= n && newy >= 1 && newy <= m && mp[newx][newy] != '#' && !vis[newx][newy])
            {
                vis[newx][newy] = true;
                q.push({newx, newy});
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 'N') // 小午的位置
                nx = i, ny = j;
            if (mp[i][j] == 'M') // 小枫的位置
                mx = i, my = j;
            if (mp[i][j] == '!')
                yaoshix = i, yaoshiy = j; // 找到钥匙的位置
        }
    bfs(nx, ny);  // 从小午开始bfs
    bfs2(mx, my); // 从小枫开始bfs
    // 如果小午找到钥匙，并且小枫，小枫找到出口，或者小午找到小枫，直接找到出口
    if (Ntoyaoshi && YaoshiToM && Mtochukou || Ntoyaoshi && YaoshiToM && Ntochukou)
        printf("we were here together\n");
    else if (Ntochukou)
        printf("sorry\n");
    else
        printf("NO\n");
    return 0;
}