Luogu

LOJ

分析

首先发现答案只可能是 $-1,0,1,2$ 中的一个：当图本就不连通时答案为 $0$，当图存在割点时答案为 $1$，当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$，否则答案为 $2$。

然而把整张图都建出来显然是不现实的。不难想到只把每只蛐蛐周围一圈跳蚤拿出来建图，但这样会有问题：

.**
.*#
.**

此时第二行第二列的 * 在新图中是一个割点，但它在原图中不是割点。

为了解决这个问题我们把每只蛐蛐周围两圈跳蚤都拿出来建图，然后只把里面那圈的跳蚤算成割点。

实现时可以从每只蛐蛐出发 BFS，将所有要拿出来的跳蚤都找到，并标记每只跳蚤是否处于里面一圈；然后连边跑 Tarjan 即可。

写起来有一个减小代码量的 trick：对于每只蛐蛐扩展出来的跳蚤，只 Tarjan 一次，如果 Tarjan 到的点和拿出来的点数量不同就说明不连通，这样可以省去判连通性的代码量。

根据写法可能需要判一下 $n=1$ 或 $m=1$ 时的情况。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2400000+5;

struct pair_hash {
    template<class T1,class T2>
    size_t operator ()(const pair<T1,T2>& p) const {
        return (p.first*65536+p.second)%19491001;
    }
};

int n,m,c,x[N],y[N],ans,flag[N],cnt,vis[N];
unordered_map<pair<int,int>,int,pair_hash> H,id;
queue<int> Q; vector<pair<int,int> > vec;
vector<int> E[N];

int dfn[N],low[N],tim=0;
void tarjan(int u,int f) {
    dfn[u]=low[u]=++tim; int s=0;
    for (int v:E[u]) {
        if (!dfn[v]) { ++s;
            tarjan(v,u),low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                if (flag[u]&&(f||s>1)) ans=min(ans,1);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

void bfs(int s) {
    id.clear(),cnt=0,vec.clear(); Q.push(s),vis[s]=1;
    while (!Q.empty()) {    
        int u=Q.front(); Q.pop();
        for (int i=max(1,x[u]-2);i<=min(n,x[u]+2);++i)
            for (int j=max(1,y[u]-2);j<=min(m,y[u]+2);++j) {
                if (i==x[u]&&j==y[u]) continue;
                int v;
                if (v=H[mp(i,j)]) {
                    if (!vis[v]) vis[v]=1,Q.push(v);
                } else {
                    if (!id[mp(i,j)]) id[mp(i,j)]=++cnt,vec.emplace_back(mp(i,j));
                    if (max(abs(i-x[u]),abs(j-y[u]))==1) flag[id[mp(i,j)]]=1;
                }
            }
    }
    tim=0;
    for (int i=1;i<=cnt;++i) dfn[i]=low[i]=0,E[i].clear();
    for (auto i:vec) {
        int u=id[i],v;
        if (v=id[mp(i.first+1,i.second)])
            E[u].emplace_back(v),E[v].emplace_back(u);
        if (v=id[mp(i.first,i.second+1)])
            E[u].emplace_back(v),E[v].emplace_back(u);
    }
    tarjan(1,0);
    if (tim!=cnt) ans=0;
    for (int i=1;i<=cnt;++i) flag[i]=0;
}

int main() {
    int T=read();
    while (T--) {
        H.clear();
        n=read(),m=read(),c=read();
        for (int i=1;i<=c;++i) vis[i]=0;
        for (int i=1;i<=c;++i) {
            x[i]=read(),y[i]=read();
            H[mp(x[i],y[i])]=i;
        }
        if (1ll*n*m-c<2) { puts("-1"); continue; }
        ans=2;
        if (n==1||m==1) ans=1;
        for (int i=1;i<=c;++i) if (!vis[i]) bfs(i);
        if (1ll*n*m-c==2&&ans) { puts("-1"); continue; }
        printf("%d\n",ans);
    }
    return 0;
}