题目描述
跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个行
列的网格上排兵布阵。其中的
个格子中
,每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。
我们称占据的格子有公共边的两只跳蚤是相邻的。
我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,或存在另一只跳蚤与这两只跳蚤都连通。
现在,蛐蛐国王希望,将某些(个,
个或多个)跳蚤替换成蛐蛐,使得在此之后存在至少两只跳蚤不连通。
例如:我们用图左表示一只跳蚤,用图右表示一只蛐蛐,那么图描述了一个
的情况。
这种情况下蛐蛐国王可以通过将第行第
列,和第
行第
列的两只跳蚤替换为蛐蛐,从而达成他的希望,如图
所示。并且,不存在更优的方案,但是可能存在其他替换
只跳蚤的方案。
你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成,你还需要最小化被替换的跳蚤的个数。
输入格式
每个输入文件包含多组数据。
输入文件的第一行只有一个整数,表示数据的组数。保证
。
接下来依次输入组数据,每组数据的第一行包含三个整数
。保证
。
接下来行,每行包含两个整数
,表示第
行,第
列的格子被一个蛐蛐占据
。每一组数据当中,同一个蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
输出格式
对于每一组数据依次输出一行答案。
如果这组数据中,蛐蛐国王的希望不能被达成,输出。否则,输出被替换的跳蚤的个数的最小值。
题目解析
说实话,我真的很佩服那些在考场上能把这题AC的爷爷们。这种大分类讨论题,居然有人能绕开所有坑。
在同步赛考场上,我乱写了一个做法交上去居然还有56分真感动。(大概是因为特判了或
)
言归正传。我们来讨论一下正解。
方便起见,我们把跳蚤格子称为白格,蛐蛐格子称为黑格。
首先,我们可以发现,如果有解,答案总是不会超过的。因为我们总能在网格中找到一个角。
于是我们先判断有没有解。显然,如果网格中白格少于2个,肯定是无解的。如果白格恰好有2个,如果它们是四连通意义下相邻的,也是无解的。否则,一定有解。
如果确定了有解,我们只需要确定答案能否为0或1。
在此之前,我们先特判或
的情况。
考虑为0的情况,即白格是不连通的。什么情况下可能不连通呢?我们发现,如果要让白格不连通,一定是一些黑格组成的八连通分量把某些白格围在了内部。由于黑格数量不多,我们可以枚举所有黑格的八连通分量,对其周围的白格DFS一波就好了。但是我们DFS所有白格是的,考虑优化。
注意到与黑格八连通的白格才有用,其他白格其实是没有意义的。于是我们预处理这些格子,DFS时只走这些格子即可。
再来考虑1的情况,即我们加一个黑格即可把某些白格围住,就像一个环上的缺口。如果我们把所有白格在四连通意义下抽象成一个图,可以发现这样的白格其实是这个图的割点。于是问题转化成了求图是否有割点。求所有白格的割点是的,考虑优化。
注意到如果有割点,这个割点一定是与某个黑格八连通意义下相邻的。于是所有与某个黑格八连通意义下相邻的白格是要加入图中的。但是如果只搜这些白格,原来不是割点的格子可能就变成割点了。于是与这些白格八连通的白格也要加入图中,但是这些格子不能成为割点。于是再对这些白格DFS一波就好了。
判断白格是否在图中可以用哈希或map实现。如果用哈希,时间复杂度是。
这题写起来简直了…… 一言不合就5K。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; int n,m,idx; const int mo=5110031; const int maxn=(int)(3e6)+5; LL key[mo]; int val[mo]; int id[mo]; int vis[maxn]; int dfn[maxn]; int low[maxn]; inline void ins(int x,int y,int v) { LL c=1LL*(x-1)*m+y; int p=c%mo; while(key[p]!=c && key[p]!=-1) { p++;if(p>=mo) p-=mo; } if(key[p]==-1) key[p]=c,val[p]=v,id[p]=++idx; else val[p]=min(val[p],v); } inline int hs(int x,int y,int v) { LL c=1LL*(x-1)*m+y; int p=c%mo; while(key[p]!=c && key[p]!=-1) { p++;if(p>=mo) p-=mo; } if(key[p]>=0 && val[p]==v) return id[p]; return 0; } inline bool inlaw(int x,int y) { return x>=1 && y>=1 && x<=n && y<=m; } inline int iabs(int x) { return x>=0?x:-x; } vector<pii> pt[4]; void init() { idx=0; REP(i,1,3) pt[i].clear(); memset(key,-1,sizeof(key)); memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); } pii stk[maxn]; int top,co; void dfsa(int x,int y) { int c=hs(x,y,1); vis[c]=co;stk[++top]=make_pair(x,y); REP(p,-1,1) REP(q,-1,1) { int nx=x+p,ny=y+q; if(inlaw(nx,ny)) { int w=hs(nx,ny,1); if(w && !vis[w]) dfsa(nx,ny); } } } void dfsb(int x,int y) { int c=hs(x,y,2); vis[c]=co; REP(k,0,3) { int nx=x+dx[k],ny=y+dy[k]; if(inlaw(nx,ny)) { int w=hs(nx,ny,2); if(w && !vis[w]) dfsb(nx,ny); } } } int gcnt; void dfsc(int x,int y,int f) { int c=max(hs(x,y,2),hs(x,y,3)),cnt=0; dfn[c]=low[c]=++idx; REP(k,0,3) { int nx=x+dx[k],ny=y+dy[k]; if(inlaw(nx,ny)) { int w=max(hs(nx,ny,2),hs(nx,ny,3)); if(!w) continue; if(!dfn[w]) { dfsc(nx,ny,1);++cnt; low[c]=min(low[c],low[w]); if(low[w]>=dfn[c] && f && hs(x,y,2)) gcnt++; } else low[c]=min(low[c],dfn[w]); } } if(!f && cnt>1 && hs(x,y,2)) gcnt++; } int spc[maxn]; void solve() { init();co=0; int c; read(n);read(m);read(c); REP(i,1,c) { int x,y; read(x);read(y); REP(p,-2,2) REP(q,-2,2) { int nx=x+p,ny=y+q; if(inlaw(nx,ny)) ins(nx,ny,max(iabs(p),iabs(q))+1); } } REP(i,0,mo-1) if(key[i]!=-1) { pt[val[i]].push_back(make_pair((key[i]-1)/m+1,(key[i]-1)%m+1)); } LL tot=1LL*n*m-c; if(tot<2) { printf("-1\n"); return; } if(tot==2) { REP(x,1,n) REP(y,1,m) if(!hs(x,y,1)) { REP(k,0,3) { int nx=x+dx[k],ny=y+dy[k]; if(inlaw(nx,ny) && !hs(nx,ny,1)) { printf("-1\n"); return; } } } } if(n==1 || m==1) { if(c==0) { printf("1\n"); return; } spc[0]=0; for(int i=0;i<pt[1].size();i++) { int x=pt[1][i].first,y=pt[1][i].second; if(n==1) spc[++spc[0]]=y; else spc[++spc[0]]=x; } if(n==1) spc[++spc[0]]=m+1; else spc[++spc[0]]=n+1; sort(spc+1,spc+spc[0]+1); int spcnt=0,sptot=spc[0];spc[0]=0; REP(i,1,sptot) if(spc[i]-spc[i-1]>1) spcnt++; if(spcnt>1) { printf("0\n"); return; } printf("1\n"); return; } int succ=0; for(int i=0;i<pt[1].size();i++) { int x=pt[1][i].first,y=pt[1][i].second; int p=hs(x,y,1); if(!vis[p]) { top=0; ++co;dfsa(x,y); ++co;int fl=0; REP(k,1,top) { int x=stk[k].first,y=stk[k].second; REP(d,0,3) { int nx=x+dx[d],ny=y+dy[d],ta; if(inlaw(nx,ny) && (ta=hs(nx,ny,2))) { if(!fl) { if(!vis[ta]) dfsb(nx,ny),fl=1; } else if(vis[ta]!=co) succ=1; } } } if(succ) break; } } if(succ) { printf("0\n"); return; } idx=gcnt=0; for(int i=0;i<pt[1].size();i++) { int x=pt[1][i].first,y=pt[1][i].second; REP(k,0,3) { int nx=x+dx[k],ny=y+dy[k],ta; if(inlaw(nx,ny) && (ta=hs(nx,ny,2))) { if(!dfn[ta]) dfsc(nx,ny,0); } } } if(gcnt) { printf("1\n"); return; } printf("2\n"); } int main() { int T; read(T); while(T--) solve(); return 0; } |