Codeforces #191 Div2. D. Block Tower

Div2 Dの割に簡単な問題。
http://codeforces.com/contest/327/problem/D

問題

2次元グリッド上に青い塔と赤い塔を建てたい。
グリッド上には以下のステップをとることができる。

• 空きセルに青い塔を建てる。青い塔には１つ100人が住める。
• 空きセルに赤い塔を建てる。赤い塔はいずれかの隣接マスに青い塔がなければ建てられない。青い塔には１つ100人が住める。
• すでに建てられた塔を破壊する。

グリッド上いくつかのマスには穴が開いていて塔が立てられない。
グリッド上に住める人の数を最大化するようステップを構築せよ。

解法

以下のプロセスをとればよい。

• まず全空きマスに青い塔を建てる
• その後、空きマスを見つけるごとにDFSで隣接マスをたどり、深い順に青い塔を壊して赤い塔を建てる

2つ目のステップは、言い方を変えると連続する青い塔のグループで1つを残して遠い順に赤くしていくことに相当する。

int H,W;
string S[501];
vector<pair<char,int> > V;
int stat[501][501];

void dfs(int cx,int cy,int first) {
	int i;
	int dx[]={0,0,1,-1};
	int dy[]={1,-1,0,0};
	S[cy][cx]='#';
	FOR(i,4) {
		int tx=cx+dx[i];
		int ty=cy+dy[i];
		if(tx<0 || tx>=W || ty<0 || ty>=H || S[ty][tx]!='B') continue;
		dfs(tx,ty,0);
	}
	if(first==0) {
		V.push_back(make_pair('D',cy*1000+cx));
		V.push_back(make_pair('R',cy*1000+cx));
	}
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin >> H >> W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) if(S[y][x]!='#') {
		V.push_back(make_pair('B',y*1000+x));
		S[y][x]='B';
	}
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='B') dfs(x,y,1);
	
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%c %d %d\n",V[i].first,1+V[i].second/1000,1+V[i].second%1000);
	
	return;
}

まとめ

いまいち何がさせたかったのかわからない問題。