并查集

这道题用并查集的思路也可以做。

#include <iostream>
using namespace std;
#define int long long
const int N=1010;
int p[N*N];
string s[N];
bool k[N*N],f[N*N],g[N*N];
int find(int x){
    if(p[x]==x){
        return x;
    }
    return p[x]=find(p[x]);
}
void add(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y){
        return;
    }
    p[x]=y;
    k[y]|=k[x];
    f[y]|=f[x];
    g[y]|=g[x];
}
bool test(int n,int m,int w){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int id=(i-1)*m+j;
            if(s[i][j]!='#'){
                if(i>1&&s[i-1][j]!='#'){
                    add(id,id-m);
                }
                if(j>1&&s[i][j-1]!='#'){
                    add(id,id-1);
                }
            }
        }
    }
    w=find(w);
    return f[w];
}
signed main(){
    int n,m;
    cin>>n>>m;
    int w=0;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
        for(int j=1;j<=m;j++){
            int id=(i-1)*m+j;
            p[id]=id;
            if(s[i][j]=='N'){
                w=id;
            }
            if(s[i][j]=='!'){
                k[id]=true;
            }
            if(s[i][j]=='@'){
                f[id]=true;
            }
            if(s[i][j]=='M'){
                g[id]=true;
            }
            if(s[i][j]!='#'&&s[i][j]!='$'){
                if(i>1&&s[i-1][j]!='#'&&s[i-1][j]!='$'){
                    add(id,id-m);
                }
                if(j>1&&s[i][j-1]!='#'&&s[i][j-1]!='$'){
                    add(id,id-1);
                }
            }
        }
    }
    w=find(w);
    if(g[w]){
        if(f[w]){
            cout<<"we were here together";
        }
        else{
            if(k[w]){
                if(test(n,m,w)){
                    cout<<"we were here together";
                }
                else{
                    cout<<"NO";
                }
            }
            else{
                cout<<"NO";
            }
        }
    }
    else{
        if(f[w]){
            cout<<"sorry";
        }
        else{
            cout<<"NO";
        }
    }
    return 0;
}

不一定非得 $BFS$，思路很多种。