読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

yukicoder : No.13 囲みたい!

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

問題

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

解法

まず、隣接した同数値のマス対を探す。
次に、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はこういうグリッド系の問題が多いような気がするけど、気のせいかな。

広告を非表示にする