题面
https://www.luogu.org/problem/P1173
题解
终于调出来了呢。
这道题和【NOI2015】小园丁和老司机一样，都是码量大的神仙题，不过写小园丁和老司机的时候，没有花太长时间调试，但是这题...真的是自闭了。
首先，答案肯定在$-1$，$0$，$1$，$2$之间。
你可能觉得我在耍流氓，因为我看了题解，现在我就来证明答案一定小于等于$2$。
我们只考虑围住一个白棋子的四周，它就孤立了，所以答案肯定小于等于$4$。
我们肯定在图中找一个“气”数最小的点围住，我用反证法，让我构造一个棋局，使每个点的气数都大于等于$3$。
我们考虑黑棋和白棋相接触处的轮廓线，对于和黑棋相接触的白棋，假设它下面是黑棋，下一个白棋只有两种放置方式
这个过程是不能停下来的，因为一旦停下来，就露出了破绽，使得气数为$2$。
所以这个轮廓线会最终形成一个螺旋，只有一个无限大的二维空间才能放下这个无限大的螺旋，所以不存在，假设不成立，原命题得证。
我们把长宽至少有一个为$1$的特判掉。
再一个结论，当长宽都至少为$2$时，任意一种切割，都是两个或两个以上的黑棋形成的，这是一个显然的结论，但是是本题的突破口。
我们把一个黑棋上下左右形成的$5 \times 5$方块里棋子挖出来建图，因为只要它们是有用的。
如果对于一个黑棋的联通块，它旁边的白棋分别属于不同的联通块，则此黑棋的联通块把白棋的联通块切割了，输出$0$。
如果图中存在割点（且割点旁边$3 \times 3$的区域内有黑棋），则输出$1$。
反之，则输出$2$。
我们要支持从集合内插入元素，$O(1)$查找，确定集合中元素的$id$，用$hash$表实现（用$sort$建边亦可，但是八个$cmp$八个$sort$有点麻烦）
$hash$函数肯定是我们最喜欢的$1000000007$啦，奇怪了，不是我最喜欢的吗？
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #define ri register int #define N 2500500 using namespace std; const int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0}; int dfn[N],low[N],col[N],root,n,m,c,ccol; vector<int> to[N]; bool del[N],can; bool vi[100050],vvv[N]; int cc,co; int x[N],y[N],id[N]; void add_edge(int u,int v) { to[u].push_back(v); to[v].push_back(u); } bool cmp(int a,int b) { return x[a]<x[b] || x[a]==x[b] && y[a]<y[b]; } struct hash_table{ #define SIZ 1233107 vector<int> h[SIZ]; void clear() { for (ri i=0;i<SIZ;i++) h[i].clear(); } void add(int cx,int cy,int s) { int g=((cx*1LL*1000000007)%SIZ+cy)%SIZ; for (ri i=0;i<h[g].size();i++) if (x[h[g][i]]==cx && y[h[g][i]]==cy) { if (s) del[h[g][i]]=1; return; } h[g].push_back(++cc); x[cc]=cx; y[cc]=cy; if (s) del[cc]=1; return; } int find(int cx,int cy) { int g=((cx*1LL*1000000007)%SIZ+cy)%SIZ; for (ri i=0;i<h[g].size();i++) if (x[h[g][i]]==cx && y[h[g][i]]==cy) return h[g][i]; return 0; } } H; void init() { H.clear(); for (ri i=1;i<=cc;i++) to[i].clear(); for (ri i=1;i<=cc;i++) del[i]=0; for (ri i=1;i<=cc;i++) dfn[i]=low[i]=0; cc=0; co=0; can=0; } bool check(int u) { for (ri dx=-1;dx<=1;dx++) for (ri dy=-1;dy<=1;dy++) { if (del[H.find(x[u]+dx,y[u]+dy)]) return 1; } return 0; } void tarjan(int u,int ccc) { dfn[u]=low[u]=++co; col[u]=ccc; int rs=0; for (ri i=0;i<to[u].size();i++) { int v=to[u][i]; if (!dfn[v]) { rs++; tarjan(v,ccc); low[u]=min(low[u],low[v]); if (low[v]>=dfn[u] && u!=root && check(u)) can=1; } else { low[u]=min(low[u],dfn[v]); } } if (u==root && rs>=2 && check(u)) can=1; } int num(int x,int y) {return (x-1)*m+y;} bool checkf1() { memset(vi,0,sizeof(vi)); for (ri i=1;i<=cc;i++) if (del[i]) vi[num(x[i],y[i])]=1; for (ri i=1;i<=n;i++) for (ri j=1;j<=m;j++) if (!vi[num(i,j)]) { if (i+1<=n && !vi[num(i+1,j)]) return 1; if (j+1<=m && !vi[num(i,j+1)]) return 1; } return 0; } bool bfs(int cur) { vvv[cur]=1; int cx=x[cur],cy=y[cur]; for (ri i=0;i<4;i++) { int nx=cx+dx[i],ny=cy+dy[i]; if (nx<1 || nx>n || ny<1 || ny>m) continue; int t=H.find(nx,ny); if (!del[t]) { if (ccol==-1) ccol=col[t]; if (col[t]!=ccol) return 0; } else { if (!vvv[t] && !bfs(t)) return 0; } } return 1; } bool dfs() { memset(vvv,0,sizeof(vvv)); for (ri i=1;i<=cc;i++) if (del[i] && !vvv[i]) { ccol=-1; if (!bfs(i)) return 1; } return 0; } int a[100050]; int solve() { int cn=0; if (m==1) { for (ri i=1;i<=cc;i++) if (del[i]) a[++cn]=x[i]; } else { for (ri i=1;i<=cc;i++) if (del[i]) a[++cn]=y[i]; } sort(a+1,a+cn+1); a[0]=0; if (m==1) a[cn+1]=n+1; else a[cn+1]=m+1; int cnt=0; for (ri i=0;i<=cn;i++) if (a[i]+1!=a[i+1]) cnt++; if (cnt==1) return 1; else return 0; } int main() { int T,t,tx,ty; scanf("%d",&T); while (T--) { init(); scanf("%d %d %d",&n,&m,&c); for (ri i=1;i<=c;i++) { scanf("%d %d",&tx,&ty); for (ri dx=-2;dx<=2;dx++) for (ri dy=-2;dy<=2;dy++) { if (tx+dx<1 || tx+dx>n || ty+dy<1 || ty+dy>m) continue; if (dx==0 && dy==0) H.add(tx+dx,ty+dy,1); else H.add(tx+dx,ty+dy,0); } } for (ri i=1;i<=cc;i++) id[i]=i; sort(id+1,id+cc+1,cmp); for (ri i=1;i<=cc;i++) if (!del[id[i]]) { t=H.find(x[id[i]]+1,y[id[i]]+0); if (t&&!del[t]) add_edge(id[i],t); t=H.find(x[id[i]]+0,y[id[i]]+1); if (t&&!del[t]) add_edge(id[i],t); } can=0; int ccc=0; for (ri i=1;i<=cc;i++) if (!del[i] && !dfn[i]) root=i,tarjan(i,++ccc); if (n*1LL*m-c<=1 || n*1LL*m-c==2 && checkf1()) puts("-1"); else if (n==1 || m==1) printf("%d\n",solve()); else if (dfs()) puts("0"); else if (can) puts("1"); else puts("2"); } return 0; }
原文：https://www.cnblogs.com/shxnb666/p/11407802.html