题解：CF2097B Baggage Claim

MattL · 2025-04-30 14:17:03 · 题解

题意

网格图中有一条路径，每一步只能走到相邻的边。给出第奇数步的点的坐标，问有多少条路径能满足不走重复的格子？

分析

• 当给出的两个相邻节点的曼哈顿距离（即要走的步数）不等于 2 时，显然无解。形式地，对于 (x_1,y_1) 与 (x_2,y_2) 节点，满足 |x_1-x_2|+|y_1-y_2|\neq 2，则无解。
• 当给出的两个相邻节点为直线时，夹着的点只有一个可能，即中间的那个点。对于 (x_1,y_1) 与 (x_2,y_2) 节点，满足 |x_1-x_2|=2,|y_1-y_2|\neq 0 或 |x_1-x_2|=0,|y_1-y_2|\neq 2，我们只能选择 (\frac{x_1+x_2}{2},\frac{y_1+y_2}{2})。
• 当给出的两个相邻节点为折线时，夹着的点有两个可能。形式地，对于 (x_1,y_1) 与 (x_2,y_2) 节点，满足 |x_1-x_2|=0 或 |y_1-y_2|=0，我们可以选择 (x_1,y_2) 与 (x_2,y_1)。

我们来考虑如何做到不走重复的格子。对于给出的相邻两个格子，我们只能选择一个。于是我们想到把这件事抽象成一张图，一条边只能选择一个节点。特别地，对于只有一种选择的，我们连自环。最后，我们希望一个节点只能被选一次，每一条边都要选其中的一个顶点。

显然这样建图不一定都联通，会形成很多个连通块。我们考虑对于每一个连通块：

• 如果这个连通块有多个环，即 E>V，那么一定无解。因为一条边需选择一个节点，总共需选择 E 个节点，而节点没那么多。
• 若这个连通块仅有一个环，即 E=V，那么分两种情况
  1. 这个环是个自环，没有选择的余地，答案为 1。
  2. 这个环是非退化环（即自环），对于每条边都可以同时选其中一个和另外一个，答案为 2。
• 若这个连通块是一棵树，即 E=V-1，那么我只需要在这棵树里面选择一个不要的节点，其他点就都确定了。答案为 V。

最后，根据乘法原理把答案乘起来即可。

注意：无解时请勿直接退出，还要清空。

代码

#include <bits/stdc++.h>
using namespace std;
#define ls (now<<1)
#define rs (now<<1|1)
#define LL long long
#define f(i,n) for(int i=1;i<=n;i++)
#define f_(i,n) for(int i=n;i>=1;i--)
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define ff_(i,a,b) for(int i=a;i>=b;i--)
#define pi pair<int,int>
#define pb push_back
#define vi vector<int>
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define fs(i,s) for(int i=0;i<s.size();i++)
#define re return
#define con continue
#define bre break
#define mkp make_pair
#define umap unordered_map
#define ld long double
const int N=3e6+10,M=1e3+100;
int n,m,k,x[N],y[N],xx[N],yy[N];
int chox[N],choy[N];
bool mp[M][M];
int num[M][M],cnt,cntm;
vector<int> to[N];
void add(int x1,int y1,int x2,int y2){
    if(!num[x1][y1]){
        num[x1][y1]=++cnt;
        xx[cnt]=x1,yy[cnt]=y1;//还需要记录节点以便清空 
    }
    if(!num[x2][y2]){
        num[x2][y2]=++cnt;
        xx[cnt]=x2,yy[cnt]=y2;
    }
    to[num[x1][y1]].pb(num[x2][y2]);
    to[num[x2][y2]].pb(num[x1][y1]);
}
const int mod=1e9+7;
LL ans;
int sum,numm;
bool ok,vis[N];
void dfs(int k){
    vis[k]=1;
    numm++;
    sum+=to[k].size();
    for(auto i:to[k]){
        if(!vis[i])
            dfs(i);
        if(i==k)ok=1;
    }
}
void solve(){
    cin>>n>>m>>k;
    k++;cnt=0;ans=1;
    f(i,k)cin>>x[i]>>y[i];
    f(i,k-1){
        if(abs(x[i]-x[i+1])+abs(y[i]-y[i+1])!=2){
            cout<<0<<'\n';
            f(o,cnt)vis[o]=0,to[o].clear(),num[xx[o]][yy[o]]=0;
            re;
        }if(x[i]==x[i+1]){
            add(x[i],(y[i]+y[i+1])/2,x[i],(y[i]+y[i+1])/2);
        }else if(y[i]==y[i+1]){
            add((x[i]+x[i+1])/2,y[i],(x[i]+x[i+1])/2,y[i]);
        }else{
            add(x[i],y[i+1],x[i+1],y[i]);
        }
    }
    f(i,cnt){
        if(!vis[i]){
            numm=sum=ok=0;dfs(i);sum>>=1;
            if(sum>numm){
                cout<<0<<'\n';
                f(o,cnt)vis[o]=0,to[o].clear(),num[xx[o]][yy[o]]=0;
                re;
            }
            if(sum==numm){
                if(!ok)ans=1ll*ans*2%mod;
            }else{
                ans=1ll*ans*numm%mod;
            }
        }
    }
    f(o,cnt)vis[o]=0,to[o].clear(),num[xx[o]][yy[o]]=0;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T; 
    cin>>T;
    while(T--)
        solve();
    return 0;
}