Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 341 LandAndSea

|  SRM 341 LandAndSea - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 341 LandAndSea - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7512

  • 実装間に合わず。
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class LandAndSea {
	int[][] map;
	int[][] maplevel;
	int[][] islid;
	int[][] islinfo = new int[1000][4];
	int[] levels;
	int idx = 1;
	boolean[][] graph;
	boolean[][] visited;
	
	int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
	int[] dy = {0, 1, 0, -1, -1, 1, -1, 1};
	
	public int dfs(int isl) {
		int r = 0; 
		for (int i = 1 ; i < idx ; i++) {
			if (graph[isl][i]) {
				r = Math.max(r, dfs(i) + 1);
			}
		}
		return r;
	}
	
	public void paint(int x, int y, int isl) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 4 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (tx <= -1 || ty <= -1 || tx >= visited[0].length || ty >= visited.length) {
					continue;
				}
				if (islid[ty][tx] != isl && !visited[ty][tx]) {
					visited[ty][tx] = true;
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}
	
	public void island(int x, int y) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		islid[y][x] = idx;
		islinfo[idx][0] = x;
		islinfo[idx][1] = y;
		islinfo[idx][2] = x;
		islinfo[idx][3] = y;
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 8 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (map[ty][tx] == 1 && islid[ty][tx] == 0) {
					islid[ty][tx] = idx;
					islinfo[idx][0] = Math.min(islinfo[idx][0], tx);
					islinfo[idx][1] = Math.min(islinfo[idx][1], ty);
					islinfo[idx][2] = Math.max(islinfo[idx][2], tx);
					islinfo[idx][3] = Math.max(islinfo[idx][3], ty);
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}

	
	public int[] howManyIslands(String[] seaMap) {
		int w = seaMap[0].length();
		int h = seaMap.length;
		map = new int[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (seaMap[i].charAt(j) == 'x') {
					map[i+1][j+1] = 1;
					System.out.print(1);
				} else {
					System.out.print(0);
				}
			}
			System.out.println();
		}
		
		levels = new int[501];
		maplevel = new int[h+2][w+2];
		islid = new int[h+2][w+2];
		idx = 1;
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (map[i][j] == 1 && islid[i][j] == 0) {
					island(j, i);
					idx++;
				}
			}
		}
		
		graph = new boolean[idx][idx];
		for (int i = 1 ; i < idx ; i++) {
			visited = new boolean[h+2][w+2];
			paint(0, 0, i);
			for (int y = 0 ; y < h ; y++) {
				for (int x = 0 ; x < w ; x++) {
					int idx = (islid[y][x]);
					if (idx != i && idx >= 1 && !visited[y][x]) {
						graph[i][idx] = true;
					}
				}
			}
		}
		
		for (int i = 1 ; i < idx ; i++) {
			levels[dfs(i)]++;
		}
		int maxlevel = -1;
		for (int l = 0 ; l < 500 ; l++) {
			if (levels[l] >= 1) {
				maxlevel = l;
			}
		}
		int[] ans = new int[maxlevel+1];
		for (int l = 0 ; l <= maxlevel ; l++) {
			ans[l] = levels[l];
		}
		System.out.println(Arrays.toString(ans));
		return ans;
	}
}