Codeforces 135 D. Cycle
問題
0と1からなるグリッドが与えられる。
このなかで、coolなcycleのうち、最も長さの長いものの長さを求めよ。
coolなcycleとは以下を満たすcycleである。
- '1'からなるセルの集合である。
- cycleに属する全ての'1'は、(辺を共有して)cylceの別の'1'ちょうど2個に隣接している。
- 内部に'1'を含まない。
制約条件
幅,高さ≦1000
方針
cycleは、
11 11
のような場合だけ例外で、それ以外の場合は必ず内部に'0'を含む。
111 111
のようなものはcycleでないことに注意。
そのため、0を塗りつぶして、0の領域を囲む1が、cycleを作っているかを調べればよい。
0を塗りつぶしながら、
- 隣接していた1をリストに入れる
- グリッドの外にはみ出ることができたか
を同時に調べる。
グリッドの外にはみ出ることができたら、1で囲まれていないので、それはcycleではない。
隣接していた1がただ一つの島(連結成分)からなることが、cycleであることの必要条件である。
島は、最初に深さ優先で'1'のかたまりを調べておく。
これに加えて、リストの1が全部、二つのほかの1と隣接していればcycleである必要十分条件になる。
ソースコード
const int dy[]={-1,0,1,0},dx[]={0,-1,0,1}; int h,w; string in[1002]; int color[1002][1002],C; bool v[1002][1002]; void paint(int y,int x,int c){ color[y][x]=c; rep(d,4){ int ny=y+dy[d], nx=x+dx[d]; if(in[ny][nx]=='1'&&color[ny][nx]<0)paint(ny,nx,c); } } bool ok; set<int> s; int st[1010*1010],sz; bool cycle[1002][1002]; void rec(int y,int x){ v[y][x]=1; for(int dy=-1;dy<2;dy++)for(int dx=-1;dx<2;dx++)if(dy||dx){ int ny=y+dy, nx=x+dx; if(ny<0||nx<0||ny>=h||nx>=w){ ok=0; continue; } if(in[ny][nx]=='0'&&!v[ny][nx])rec(ny,nx); if(in[ny][nx]=='1'){ s.insert(color[ny][nx]); if(!cycle[ny][nx])cycle[ny][nx]=1,st[sz++]=ny*1010+nx; } } } bool iscycle(int y,int x){ v[y][x]=1; int deg=0; rep(d,4){ int ny=y+dy[d], nx=x+dx[d]; if(ny<0||nx<0||ny>=h||nx>=w||!cycle[ny][nx])continue; deg++; if(!v[ny][nx]&&!iscycle(ny,nx))return 0; } return deg==2; } void run() { cin>>h>>w; rep(i,h){ cin>>in[i+1]; in[i+1]="0"+in[i+1]+"0"; } h+=2; w+=2; in[0]=in[h-1]=string(w,'0'); int ans=0; rep(i,h-1)rep(j,w-1){ if(in[i][j]=='1'&&in[i+1][j]=='1'&&in[i][j+1]=='1'&&in[i+1][j+1]=='1') ans=4; } memset(color,-1,sizeof(color)); memset(v,0,sizeof(v)); memset(cycle,0,sizeof(cycle)); C=0; rep(i,h)rep(j,w)if(in[i][j]=='1'&&color[i][j]<0)paint(i,j,C++); rep(i,h)rep(j,w)if(in[i][j]=='0'&&!v[i][j]){ s.clear(); ok=1; sz=0; rec(i,j); ok&=s.size()==1; rep(k,sz)v[st[k]/1010][st[k]%1010]=0; ok&=iscycle(st[0]/1010,st[0]%1010); if(ok)ans=max(ans,sz); rep(k,sz)cycle[st[k]/1010][st[k]%1010]=0; } cout<<ans<<endl; }