yukicoder : No.13 囲みたい！

☆３つはまだ割と簡単。
http://yukicoder.me/problems/37

問題

W*Hの２次元グリッドがある。
各セルには数値が割り振られている。
ある数値のセル同士を連結し、４点以上からなる閉路が作れるか。

解法

まず、隣接した同数値のマス対を探す。
次に、BFSでその隣接マスの直接移動以外で、他のマスをたどって元の隣接マスにたどり着けるか判定すればよい。

int W,H;
int M[101][101];

int okok(int sy,int sx,int dir) {
	int ty=sy,tx=sx,i;
	if(dir==0) tx++;
	if(dir==1) ty++;
	
	int vis[101][101];
	ZERO(vis);
	queue<int> Q;
	Q.push(sy*100+sx);
	vis[sy][sx]=1;
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		int cy=k/100,cx=k%100;
		if(cy==ty && cx==tx) return 1;
		FOR(i,4) {
			int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
			if(cx==sx&&cy==sy&&i==dir) continue;
			int ttx=cx+dx[i],tty=cy+dy[i];
			if(ttx<0 || ttx>=W || tty<0 || tty>=H) continue;
			if(vis[tty][ttx] || M[tty][ttx]!=M[cy][cx]) continue;
			vis[tty][ttx]=1;
			Q.push(tty*100+ttx);
		}
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H;
	FOR(y,H) FOR(x,W) cin>>M[y][x];
	FOR(y,H) FOR(x,W-1) if(M[y][x]==M[y][x+1] && okok(y,x,0)) return _P("possible\n");
	FOR(y,H-1) FOR(x,W) if(M[y+1][x]==M[y][x] && okok(y,x,1)) return _P("possible\n");
	_P("impossible\n");
}

まとめ

なんかyukicoderはこういうグリッド系の問題が多いような気がするけど、気のせいかな。