前言

真是一道翔题。

草率题解

-1 的情况很好判，只有两种情况： n * m - c < 2 或者 n * m - c = 2 且两个格子相邻。

对于 x 坐标，我们大力将前两行、后两行、每一个点的上一行、所在行、下一行这些行离散化出来。

对于每一行，我们找出一些关键点，将一行分为若干段，将每一段看做一个点，上下左右相邻的段连边，跑Tarjan判割点。

怎么找关键点？对于每一个点，它左右距离2范围内，上下距离1 范围内的都拿出来就好了。

常数真大。

代码

#include 
    
     #define clr(x) memset(x,0,sizeof x)#define For(i,a,b) for (int i=(a);i<=(b);i++)#define Fod(i,b,a) for (int i=(b);i>=(a);i--)#define fi first#define se second#define pb(x) push_back(x)#define mp(x,y) make_pair(x,y)#define outval(x) cerr<<#x" = "<
     
      <

vi;LL read(){ LL x=0,f=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-',ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x;}const int N=100010;int T,n,m,c,s;map

,int> g;int x[N],xx[N],y[N];int dx[4]={ 0, 0, 1,-1};int dy[4]={ 1,-1, 0, 0};int Hx[N*3],cx,sum[N*3];vector

Hy[N*3];const int S=N*30;vector

e[S];int co[S];void Add_Edge(int x,int y){ if (!co[x]&&!co[y]) e[x].pb(y),e[y].pb(x);}int dfn[S],low[S],Time;int flag,cntroot=0,fir;void Tarjan(int x,int pre){ dfn[x]=low[x]=++Time; for (auto y : e[x]) if (!dfn[y]){ Tarjan(y,x); low[x]=min(low[x],low[y]); if (low[y]>=dfn[x]){ if (pre) flag=1; else cntroot++; } } else if (y!=pre) low[x]=min(low[x],dfn[y]);}bool check1(int x,int y){ return 1<=x&&x<=n&&1<=y&&y<=m;}void Solve(){ n=read(),m=read(),c=read(); g.clear(); For(i,1,c){ x[i]=read(),y[i]=read(); g[mp(x[i],y[i])]=1; } if ((LL)n*m-c<=1) return (void)puts("-1"); if ((LL)n*m-c==2){ For(i,1,n) For(j,1,m) if (!g[mp(i,j)]) For(k,0,3) if (check1(i+dx[k],j+dy[k])&&!g[mp(i+dx[k],j+dy[k])]) return (void)puts("-1"); return (void)puts("0"); } cx=0; For(i,1,c){ if (x[i]>1) Hx[++cx]=x[i]-1; Hx[++cx]=x[i]; if (x[i]

1) Hx[++cx]=2,Hx[++cx]=n-1; sort(Hx+1,Hx+cx+1); cx=unique(Hx+1,Hx+cx+1)-Hx-1; For(i,1,cx) Hy[i].clear(); For(i,1,c){ xx[i]=lower_bound(Hx+1,Hx+cx+1,x[i])-Hx; For(xp,xx[i]-1,xx[i]+1){ if (xp<1||xp>n) continue; For(yp,y[i]-1,y[i]+2) if (1<=yp&&yp<=m) Hy[xp].pb(yp); } } sum[0]=1; For(i,1,cx){ Hy[i].pb(1),Hy[i].pb(2),Hy[i].pb(m+1),Hy[i].pb(m); sort(Hy[i].begin(),Hy[i].end()); Hy[i].resize(unique(Hy[i].begin(),Hy[i].end())-Hy[i].begin()); For(j,0,(int)Hy[i].size()-2) co[sum[i-1]+j]=g[mp(Hx[i],Hy[i][j])]; sum[i]=sum[i-1]+(int)Hy[i].size()-1; } s=sum[cx]-1; For(i,1,s) e[i].clear(); For(i,1,cx) For(j,0,(int)Hy[i].size()-3) Add_Edge(sum[i-1]+j,sum[i-1]+j+1); For(i,2,cx){ int p=0; for (int j=0;j<=(int)Hy[i].size()-2;j++){ while (Hy[i-1][p+1]<=Hy[i][j]) p++; while (p<(int)Hy[i-1].size()-1&&Hy[i-1][p+1]<=Hy[i][j+1]){ Add_Edge(sum[i-2]+p,sum[i-1]+j); p++; } if (Hy[i-1][p]

1; puts(flag?"1":"2");}int main(){ T=read(); while (T--) Solve(); return 0;}

转载于:https://www.cnblogs.com/zhouzhendong/p/UOJ220.html

你可能感兴趣的文章

alue of type java.lang.String cannot be converted to JSONObject