【题解】P1173 [NOI2016] 网格

· · 题解

UPD:被叉了，加了一个特判，果然这题还是需要一点特判的...

将有蛐蛐的看做黑点，有跳蚤的看做白点。

显然答案只可以是无解或者 0,1,2。

前三个情况是显然的，最后一种情况可以分图有 3 个点和超过 3 个分别证明。

于是直接建图跑 tarjan 即可 \mathcal{O}(nm)。

然而这张图点很多但是空位很少，考虑将其缩成一个点数边数均为 \mathcal{O}(c) 的图使得缩完答案不变。

考虑只保留以下白点：

然后对于所有剩下的白点，若两个白点点在同一行或者同一列，且中间没有其它点（包括黑点黑剩下的白点），就连一条边。

注意并不是只建四连通的边。

例如这样，蓝色的格子是保留下来的点。

然后发现这张图的答案与原图的答案大多数情况是一样的，但判 -1 的时候需要特判一下若图有两个点但这两个点虽然有边但不四连通的情况，这种情况实际上会有至少三个点在里面，答案是 1，或者可以判一下 n=1,m=1 也可以。

我也不知道是不是对的，以及如果是对的咋证，反正过了所有 uoj hack 数据，欢迎继续hack。

而且考虑每个黑点只会最多贡献它周围 8 个，以及边上 4 个共 12 个点，所以一共 \mathcal{O}(c) 个点。

所以复杂度瓶颈在于建图，复杂度 \Theta(c\log c)

#include<bits/stdc++.h>
using namespace std;
//dengyaotriangle!

int n,m,c;

const int maxn=2e7+10;
struct node{
    int x,y,t;
    node(){}
    node(int x,int y,int t):x(x),y(y),t(t){}
}a[maxn];
int t,q;

bool cmp1(const node&a,const node&b){
    return a.x==b.x?(a.y==b.y?a.t<b.t:a.y<b.y):a.x<b.x;
}
bool cmp2(const node&a,const node&b){
    return a.y==b.y?a.x<b.x:a.y<b.y;
}
vector<int> adj[maxn];
int dfn[maxn],low[maxn],tfa[maxn],c1;

bool gt0;

void tarjan(int u){
    dfn[u]=low[u]=++c1;
    int cch=0;
    for(int i=0;i<(int)adj[u].size();i++){
        int v=adj[u][i];
        if(!dfn[v]){
            tfa[v]=u;
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                if(tfa[u])gt0=1;
                else cch++;
            }
        }else if(v!=tfa[u])low[u]=min(low[u],dfn[v]);
    }
    if(cch>1)gt0=1;
}
void addprem(int x,int y,int radx,int rady){
    for(int dx=-radx;dx<=radx;dx++){
        for(int dy=-rady;dy<=rady;dy++){
            int cx=x+dx,cy=y+dy;
            if(1<=cx&&cx<=n&&1<=cy&&cy<=m){
                a[++t]=node(cx,cy,0);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t_;
    cin>>t_;
    while(t_--){
        cin>>n>>m>>c;
        t=q=0;
        for(int i=1;i<=c;i++){
            int x,y;cin>>x>>y;
            addprem(x,y,1,1);
            addprem(1,y,0,0);addprem(n,y,0,0);addprem(x,1,0,0);addprem(x,m,0,0);
            a[++t]=node(x,y,-1);
        }
        addprem(1,1,2,2);addprem(1,m,2,2);addprem(n,1,2,2);addprem(n,m,2,2);
        sort(a+1,a+1+t,cmp1);
        int cp=0;node buf(INT_MAX,INT_MAX,1);
        for(int i=1;i<=t;i++){
            if(a[i].x!=buf.x||a[i].y!=buf.y){
                buf=a[i];a[++cp]=buf;
            }
        }
        t=cp;
        for(int i=1;i<=t;i++)if(a[i].t!=-1)a[i].t=++q;
        for(int i=1;i<=q;i++)adj[i].clear(),dfn[i]=0;
        c1=0;
        for(int i=2;i<=t;i++){
            if(a[i].x==a[i-1].x&&a[i].t!=-1&&a[i-1].t!=-1){
                adj[a[i].t].push_back(a[i-1].t);
                adj[a[i-1].t].push_back(a[i].t);
            }
        }
        sort(a+1,a+1+t,cmp2);
        for(int i=2;i<=t;i++){
            if(a[i].y==a[i-1].y&&a[i].t!=-1&&a[i-1].t!=-1){
                adj[a[i].t].push_back(a[i-1].t);
                adj[a[i-1].t].push_back(a[i].t);
            }
        } 
        if(q<=1){
            cout<< -1<<'\n';
            continue;
        }
        if(q==2&&adj[1].size()){
            int id[2];
            for(int i=1;i<=t;i++)if(a[i].t>=1&&a[i].t<=2)id[a[i].t-1]=i;
            if(abs(a[id[0]].x-a[id[1]].x)+abs(a[id[0]].y-a[id[1]].y)==1){
                cout<< -1<<'\n';
                continue;
            }else{
                cout<<1<<'\n';
                continue;
            }
        }
        gt0=0;
        tarjan(1);
        if(c1!=q){
            cout<< 0<<'\n';
        }else cout<<(gt0?1:2)<<'\n';
    }
    return 0;
}