TopCoder SRM 341 Div1 Medium LandAndSea

問題

n x mのグリッドで表される地図が与えられる。
'x'のマスは陸であり、'.'のマスは海である。

島とは、'x'のマスが上下左右斜めにつながった塊であり、
海は上下左右のマスとつながっている。

島のlevelとは、島に対して以下のように定義される量である。

• 他の島を囲んでいない島のlevelは0
• 他の島を囲んでいる島のlevelは、囲んでいる最大のlevelの島のlevel + 1

このとき、levelいくつの島がそれぞれいくつあるかを求めよ。

制約条件

n, m≦50

方針

一番外の海から、深さ優先探索で塗りつぶしながら、島の包含関係のグラフを作る。
グラフを作ったら、深さ優先探索でそれぞれの島のlevelを求める。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int n, h, w;
vector<string> Map;
vi e[2500];
bool v[60][60];

void nul(int y, int x, queue<int> &q){
	v[y][x] = 1;
	rep(d, 4){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0|| ny >= h || nx >= w) continue;
		if(v[ny][nx]) continue;
		if(Map[ny][nx] == 'x') q.push(ny * w + nx);
		else nul(ny, nx, q);
	}
}
void nul2(int y, int x, queue<int> &q){
	v[y][x] = 1;
	for(int dy = -1; dy < 2; dy++) for(int dx = -1; dx < 2; dx++){
		int ny = y + dy, nx = x + dx;
		if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
		if(v[ny][nx]) continue;
		if(Map[ny][nx] == '.') q.push(ny * w + nx);
		else nul2(ny, nx, q);
	}
}
void rec(int y, int x, int p){
	queue<int> q;
	nul(y, x, q);
	while(!q.empty()){
		int cy = q.front() / w, cx = q.front() % w;
		q.pop();
		if(v[cy][cx]) continue;
		int cur = n++;
		e[p].pb(cur);
		queue<int> q2;
		nul2(cy, cx, q2);
		
		while(!q2.empty()){
			int ty = q2.front() / w, tx = q2.front() % w;
			q2.pop();
			if(v[ty][tx]) continue;
			rec(ty, tx, cur);
		}
	}
}

int ans[100];
int dfs(int c){
	int res = 0;
	rep(i, e[c].size()) res = max(res, dfs(e[c][i]));
	if(e[c].size()) res++;
	if(c) ans[res]++;
	return res;
}

class LandAndSea {
	public:
	vector <int> howManyIslands(vector <string> seaMap) 
	{
		h = seaMap.size(); w = seaMap[0].size();
		
		Map.clear();
		Map.resize(h + 2);
		Map[0] = Map[h + 1] = string(w + 2, '.');
		rep(i, h) Map[i + 1] = "." + seaMap[i] + ".";
		
		h += 2; w += 2;
		
		rep(i, 2500) e[i].clear();
		memset(v, 0, sizeof(v));
		n = 1;
		rec(0, 0, 0);
		
		rep(i, 100) ans[i] = 0;
		dfs(0);
		vi v;
		rep(i, 100){
			if(!ans[i]) break;
			v.pb(ans[i]);
		}
		return v;
	}
};