Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-12SRM376 (Practice)

SRM 376 Trainyard

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

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

  • 方針を検討
    • ふつーにBFSしてカウントすればいいか
  • 実装
    • 意外と手間どう・・・ 連結であるかどうかの判定など
    • げ、もう10分もかかってる。制約小さいしかんたん実装して出しちゃえ!

システムテスト

  • あっさり落ちた。
    • やっぱ適当じゃダメだね・・・
    • 一度たどり着いた場所は枝刈りするように変更
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class Trainyard {

	class State {
		int nx;
		int ny;
		int fuel;
		State(int x, int y, int f) {
			nx = x;
			ny = y;
			fuel = f;
		}
	}
	
	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, -1, 0, 1};
	public int reachableSquares(String[] layout, int fuel) {
		int h = layout.length;
		int w = layout[0].length();
		boolean[][] visited = new boolean[h][w];
		int cnt = 0;
		int[][] mask = new int[1000][4];
		mask['S'] = new int[]{1, 1, 1, 1};
		mask['+'] = new int[]{1, 1, 1, 1};
		mask['-'] = new int[]{1, 0, 1, 0};
		mask['|'] = new int[]{0, 1, 0, 1};
		mask['.'] = new int[]{0, 0, 0, 0};
		
		Queue<State> q = new ArrayBlockingQueue<State>(10000);
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (layout[i].charAt(j) == 'S') {
					q.add(new State(j, i, fuel));
				}
			}
		}
		
		while (q.size() >= 1) {
			State stat = q.poll();
			if (stat.fuel <= -1) {
				continue;
			}
			if (!visited[stat.ny][stat.nx]) {
				visited[stat.ny][stat.nx] = true;
				cnt++;
			} else {
				continue;
			}

			char now = layout[stat.ny].charAt(stat.nx);
			for (int d = 0 ; d < 4 ; d++) {
				if (mask[now][d] >= 1) {
					int tx = stat.nx + dx[d];
					int ty = stat.ny + dy[d];
					if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
						continue;
					}
					char tow = layout[ty].charAt(tx);
					if (mask[tow][(d+2)%4] >= 1) {
						q.add(new State(tx, ty, stat.fuel - 1));
					}
				}
			}
		}
		return cnt;
	}
}

agwagw2012/03/15 15:36はじめまして、いつも楽しみに拝見させていただいております。id:agwと申します。

初学的な質問で大変申し訳ないです。Practice Roomでの過去問に対してシステムテストを行っているとのことですが、どのようにやっていらっしゃるのでしょう?

hama_DUhama_DU2012/03/15 16:02上部メニュー -> practice options -> run system test からできます

agwagw2012/03/15 16:18試してみました。どうもありがとうございます!

本番では一つでも失敗したらシステムテストを落とす、という解釈でよいのでしょうか?

hama_DUhama_DU2012/03/15 16:56もちろんそうです!
一つでも失敗したらポイントの部分が赤く表示されるので、そうなると本番ではfailed system testということになります。

agwagw2012/03/16 03:34なるほど、理解しました。どうもありがとうございます!