hama_DU@TopCoderへの道

SRM 374 PlayerExtraction

Java, div2q3, div1q2 |

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

• ごちゃごちゃ書いてあるが、要はbfsでthreshold以上の連結エリアを探して中心座標を求めるだけらしい

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class PlayerExtraction {

	public class Result implements Comparable<Result>{
		int x, y;
		public Result(int a, int b) {
			x = a;
			y = b;
		}
		public int compareTo(Result arg0) {
			if (x == arg0.x) {
				return y - arg0.y;
			}
			return x - arg0.x;
		}
	}
	public String[] extractPlayers(String[] photo, int k, int threshold) {
		threshold = (threshold + 3) / 4;
		threshold *= 4;
		List<Result> results = new ArrayList<Result>();
		int h = photo.length;
		int w = photo[0].length();
		char[][] ch = new char[h*2+2][w*2+2];
		boolean[][] visited = new boolean[h*2+2][w*2+2];
		int[] x4 = {0, 1, 0, 1};
		int[] y4 = {0, 0, 1, 1};
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				int fi = i * 2;
				int fj = j * 2;
				char c = photo[i].charAt(j);
				for (int d = 0 ; d < 4 ; d++) {
					ch[1+fi+y4[d]][1+fj+x4[d]] = c;
				}
			}
		}
		
		h *= 2;
		w *= 2;
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		char search = (char)('0' + k);
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (ch[i][j] == search && !visited[i][j]) {
					int cnt = 0;
					Queue<Integer> q = new ArrayBlockingQueue<Integer>(100000);
					q.add(i*200+j);
					int minx = 10000;
					int maxx = -10000;
					int miny = 10000;
					int maxy = -10000;
					while (q.size() >= 1) {
						cnt++;
						int stat = q.poll();
						int nx = stat % 200;
						int ny = stat / 200;
						minx = Math.min(minx, nx);
						maxx = Math.max(maxx, nx);
						miny = Math.min(miny, ny);
						maxy = Math.max(maxy, ny);
						for (int d = 0 ; d < 4 ; d++) {
							if (!visited[ny+dy[d]][nx+dx[d]] && ch[ny+dy[d]][nx+dx[d]] == search) {
								visited[ny+dy[d]][nx+dx[d]] = true;
								q.add((ny+dy[d])*200+nx+dx[d]);
							}
						}
					}
					if (cnt >= threshold) {
						int midx = (minx + maxx) / 2;
						int midy = (miny + maxy) / 2;
						results.add(new Result(midx, midy));
					}
				}
			}
		}
		
		Collections.sort(results);
		String[] res = new String[results.size()];
		for (int i = 0 ; i < res.length ; i++) {
			res[i] = "" + results.get(i).x + " " + results.get(i).y;
		}
		return res;
	}
}