题解

首先我们对于每一个位置记录四方向是否可达。

我们知道，如果 {i,j) 可达 $(k,l)$，并且 $(k,l)$ 可达 $(i,j)$，那么我们才能从这里走过去。（观察样例解释可以得到）

这就很好写了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pll pair<ll,ll>
#define mkp make_pair
#define fir first
#define sec second
const ll MAXN=1e3+13;
ll n,m,s,res;
ll mx[]={0,1,0,-1},my[]={-1,0,1,0};
bool vis[MAXN][MAXN],edge[2][4][MAXN][MAXN];
vector<ll> ans;
inline void dfs(const ll &x,const ll &y){
    res++;
    ll nx,ny;
    for(ll i=0;i<4;i++){
        nx=x+mx[i],ny=y+my[i];
        if(nx<=0||ny<=0||nx>n||ny>m) continue;
        if(edge[1][i][x][y]) continue;
        ll j;
        if(i==0) j=2;
        else if(i==1) j=3;
        else if(i==2) j=0;
        else j=1;
        if(edge[1][j][nx][ny]) continue;
        if(!edge[0][i][x][y]) continue;
        if(vis[nx][ny]) continue;
        vis[nx][ny]=true;
        dfs(nx,ny);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>s;
            for(ll k=0;k<4;k++){
                if(s>>k&1) edge[1][k][i][j]=true;
                else edge[0][k][i][j]=true;
            }
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(vis[i][j]) continue;
            res=0;
            vis[i][j]=true;
            dfs(i,j);
            ans.eb(res);
        }
    }
    sort(ans.begin(),ans.end(),greater<ll>());
    for(auto &i:ans) cout<<i<<' ';
    return 0;
}