Autumn Fest 2012 : B 3Match

続いて２問目。
ここらへんまではまだ簡単。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_02

ぷよぷよみたいな感じで、同じ数字が縦横３個並んでおり、かつ辺を共有するものをまとめて何個得られるかカウントする。

まず、３個並んでいるものを判定する。
その後、DFSで辺を共有するものを辿っていけばよい。

int H,W;
char B[101][101];
int BM[101][101];

void dfs(int y,int x,int c) {
	int dx[4]={1,-1,0,0};
	int dy[4]={0,0,1,-1};
	int lo;
	//_P("%d %d %d\n",y,x,BM[y][x]);
	
	BM[y][x]=-1;
	FOR(lo,4) {
		int ty=y+dy[lo];
		int tx=x+dx[lo];
		if(tx<0 || ty<0 || tx>=W || ty>=H) continue;
		if(BM[ty][tx]==c){
			BM[ty][tx]=-1;
			dfs(ty,tx,c);
		}
	}
	
}

void solve() {
	int x,y,i,j,p,rr,TM,TTC;
	
	GET2(&H,&W);
	FOR(y,H) GETs(B[y]);
	FOR(y,H) FOR(x,W) BM[y][x]=B[y][x]-'0';
	
	FOR(y,H) {
		FOR(x,W-2) {
			if(BM[y][x]%10 == BM[y][x+1]%10 && BM[y][x+1]%10 == BM[y][x+2]%10) {
				BM[y][x] = BM[y][x+1] = BM[y][x+2] = 10+(BM[y][x]%10);
			}
		}
	}
	FOR(y,H-2) {
		FOR(x,W) {
			if(BM[y][x]%10 == BM[y+1][x]%10 && BM[y+1][x]%10 == BM[y+2][x]%10) {
				BM[y+2][x] = BM[y+1][x] = BM[y][x] = 10+(BM[y][x]%10);
			}
		}
	}
	rr=0;
	FOR(y,H) {
		FOR(x,W) {
			if(BM[y][x]>=10) {
				rr++;
				dfs(y,x,BM[y][x]);
			}
		}
	}
	
	_P("%d\n",rr);
	return;
}

まとめ

これはやるだけゲーかな。