SRM314 D1M LandAndSea

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int h, w;
int id[55][55];
int dx[4] = { 1, 0,-1, 0};
int dy[4] = { 0, 1, 0,-1};
int dx2[8] = { 1, 1, 0,-1,-1,-1, 0, 1};
int dy2[8] = { 0, 1, 1, 1, 0,-1,-1,-1};

bool inside(int y, int x) {
	if(0 <= y && y < h && 0 <= x && x < w) return true;
	return false;
}

int counter = 0;
bool visited[55][55];
vector<string> s;
void dfs(int y, int x) {
	rep(i, 8) {
		int ny = y + dy2[i];
		int nx = x + dx2[i];

		if(inside(ny, nx) && !visited[ny][nx] && s[ny][nx] == 'x') {
			id[ny][nx] = counter;
			visited[ny][nx] = true;
			dfs(ny, nx);
		}
	}
}

int myid = -1;
bool outflag = false;
map<int, int> m;
void dfs2(int y, int x) {
	if(outflag) return;

	rep(i, 4) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		

		if(visited[ny][nx]) continue;
		if(!inside(ny, nx)) {
			outflag = true;
			return;
		}

		if(s[ny][nx] == '.') {
			visited[ny][nx] = true;
			dfs2(ny, nx);
		} else {
			int t = id[ny][nx];

			if(t != myid) {
				visited[ny][nx] = true;
				m[id[ny][nx]]++;
			} else {
				visited[ny][nx] = true;
				dfs2(ny, nx);
			}

		}
	}
}

vector<int> G[55 * 55], out;
bool used[55 * 55];
void tposo(int cur) { // topologicalsort-dfs
	used[cur] = true;
	rep(i,G[cur].size()) {
		int v = G[cur][i];
		if(!used[v]) tposo(v);
	}

	out.push_back(cur);
}


class LandAndSea {
	public:
	vector <int> howManyIslands(vector <string> seaMap) {
		s = seaMap;
		h = seaMap.size();
		w = seaMap[0].size();

		counter = 0;
		memset(id, -1, sizeof(id));
		memset(visited, false, sizeof(visited));
		rep(i, 55) G[i].clear();
		out.clear();

		vector<P> start;
		rep(i, h) {
			rep(j, w) {
				if(visited[i][j]) continue;
				if(s[i][j] == '.') continue;

				id[i][j] = counter;
				visited[i][j] = true;
				start.push_back(mp(i, j));

				dfs(i, j);
				counter++;
			}
		}

		int indeg[55 * 55];
		memset(indeg, 0, sizeof(indeg));

		rep(i, counter) {
			m.clear();
			myid = i;
			outflag = false;
			memset(visited, false, sizeof(visited));

			visited[start[i].fi][start[i].se] = true;
			dfs2(start[i].fi, start[i].se);

			if(outflag) continue;
			int parent = -1, vmax = 0;

			each(it, m) {
				if(it->second > vmax) {
					parent = it->first;
					vmax = it->second;
				}
			}

			G[i].push_back(parent);
			indeg[parent]++;
		}

		memset(used, 0, sizeof(used));
		rep(i, counter) {
			if(!used[i]) tposo(i);
		}
		reverse(out.begin(), out.end());

		map<int, int> ans;
		vector<int> dp(counter);
		rep(i, out.size()) {
			int id = out[i];
			ans[dp[id]]++;
			rep(j, G[id].size()) {
				dp[G[id][j]] = max(dp[G[id][j]], dp[id] + 1);
			}
		}

		vector<int> res(ans.size());
		rep(i, ans.size()) res[i] = ans[i];
		return res;
	}
};