TopCoder SRM 590 Div2 Medium FoxAndGo

Div2 Mediumだけど、Div1とは異なる問題なのでチャレンジ。
http://community.topcoder.com/stat?c=problem_statement&pm=12743

問題

碁盤の状態が与えられる。
ここに黒石を１つ置き、白石を取り除く。取り除ける最大の白石数を答えよ。

なお、隣接マス同士で連結された白石グループが空白マスに接していない場合、その白石グループは取り除かれる。

解法

まず、隣接マス同士で連結された白石をDFSでグループにしていく。
次に、各白石グループに接した空白マス数をカウントする。

この状態で各空白マスに黒石を置いた場合に、取り除かれる白石数をカウントし、最大値を求める。
取り除かれる白石グループは以下の通り。

• 1つも空白マスに接しない場合
• 1つだけ空白マスに接しており、その空白マスが黒石を置いた場所の場合

同じグループを重複カウントしないように注意。
ここではsetを使って重複カウントを防いでいる。

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

class FoxAndGo {
	public:
	vector<string> V;
	int W,H;
	int ID[51][51];
	int num[2501];
	set<int> E[2501];
	
	void dfs(int y,int x,int id) {
		int i,tx,ty;
		
		ID[y][x]=id;
		num[id]++;
		FOR(i,4) {
			tx=x+dx[i];
			ty=y+dy[i];
			if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
			if(V[ty][tx]=='o' && ID[ty][tx]==-1) dfs(ty,tx,id);
		}
	}
	
	int maxKill(vector <string> board) {
		int i,j,x,y,tx,ty,ret=0;
		V=board;
		H=V.size();
		W=V[0].size();
		
		MINUS(ID);
		ZERO(num);
		int id=0;
		FOR(y,H) FOR(x,W) if(board[y][x]=='o' && ID[y][x]==-1) {
			E[id].clear();
			dfs(y,x,id++);
		}
		
		FOR(y,H) FOR(x,W) if(board[y][x]=='.') {
			FOR(i,4) {
				tx=x+dx[i];
				ty=y+dy[i];
				if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
				if(V[ty][tx]=='o') E[ID[ty][tx]].insert(y*100+x);
			}
		}
		
		FOR(y,H) FOR(x,W) if(board[y][x]=='.') {
			int i,tx,ty;
			set<int> IDs;
			FOR(i,4) {
				tx=x+dx[i];
				ty=y+dy[i];
				if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
				if(V[ty][tx]=='o') IDs.insert(ID[ty][tx]);
			}
			j=0;
			ITR(it,IDs) if(E[*it].size()==1) j+=num[*it];
			ret=max(j,ret);
		}
		FOR(i,id) if(E[i].empty()) ret += num[i];
		return ret;
	}
};

まとめ

自分の書き方が悪いだけかもしれないけど、Div2 Mediumの割に長いコードになってしまった。