史山代码

题目有多种状态，可以定义4个bfs函数解决

#include<bits/stdc++.h>
using namespace std;
long long n,m,wx,wy,fx,fy,yx,yy,gx,gy;
char a[2005][2005];
bool vis[2005][2005];
struct node{
    int x,y;
};
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};//方向数组
bool flag=1;
bool bfs1(){//判断小午是否可以找到钥匙
    memset(vis,0,sizeof(vis));//重置vis数组
    queue<node> q;
    q.push({wx,wy});
    vis[wx][wy]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==yx&&t.y==yy){
            return 1;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(a[nx][ny]!='#'&&a[nx][ny]!='$'&&nx>0&&ny>0&&nx<=n&&ny<=m&&!vis[nx][ny]){
                //判断是否越界或无法通过
                q.push({nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return 0;
}
bool bfs2(){//判断小午是否可以找到小枫
    memset(vis,0,sizeof(vis));//重置vis数组
    queue<node> q;
    q.push({yx,yy});
    vis[wx][wy]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==fx&&t.y==fy){
            return 1;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(a[nx][ny]!='#'&&a[nx][ny]!='$'&&nx>0&&ny>0&&nx<=n&&ny<=m&&!vis[nx][ny]){
                //判断是否越界或无法通过
                q.push({nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return 0;
}
bool bfs3(){//判断小午是否可以在找不到小枫的情况下逃离迷宫
    memset(vis,0,sizeof(vis));//重置vis数组
    queue<node> q;
    q.push({wx,wy});
    vis[wx][wy]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==gx&&t.y==gy){
            flag=0;
            return 1;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(a[nx][ny]!='#'&&a[nx][ny]!='$'&&nx>0&&ny>0&&nx<=n&&ny<=m&&!vis[nx][ny]){
                //判断是否越界或无法通过
                q.push({nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return 0;
}
bool bfs(int sx,int sy){//判断小午是否可以在找到小枫的情况下逃离迷宫
    memset(vis,0,sizeof(vis));//重置vis数组
    queue<node> q;
    q.push({sx,sy});
    vis[sx][sy]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==gx&&t.y==gy){
            return 1;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(a[nx][ny]!='#'&&nx>0&&ny>0&&nx<=n&&ny<=m&&!vis[nx][ny]){
                //判断是否越界或无法通过，在找到小枫后可以翻越高墙
                q.push({nx,ny});
                vis[nx][ny]=1;
            }
        }
    }
    return 0;
}
int main(){
    cin >> n >> m;//输入
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j];
            if(a[i][j]=='N') wx=i,wy=j;
            if(a[i][j]=='M') fx=i,fy=j;
            if(a[i][j]=='!') yx=i,yy=j;
            if(a[i][j]=='@') gx=i,gy=j;
        }
    }
    if(bfs1()){//判断
        if(bfs2()){
            if(bfs(fx,fy)){
                cout << "we were here together";
            }else{
                cout << "NO";
            }
        }else if(bfs3()){
            cout << "sorry";
        }else{ 
            cout << "NO";
        }
    }else if(bfs3()){
        cout << "sorry";
    }else{
        cout << "NO";
    }
    
    return 0;
}