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;
}