Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 382 CollectingRiders

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

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

  • 方針を検討
    • とりあえず、dx,dy進むのにかかる手数を前計算してしまおう
  • 実装
    • BFSで実装。OFFSET = 15, MAX = 30 ぐらいでゴリゴリ書く
  • いや待て、壁があるからそう単純にはできない
    • やはり、(a,b)から(c,d)に進む最小手数を全部計算する必要が有りそうだ。
      • だが、最大サイズは10なので十分間に合うだろう。
  • 実装
    • 書いてしまったBFSの部分を使いまわす
    • 境界判定に番兵用意したいけど、最大2マス進めるし配列番号の扱いも面倒になりそうなので、愚直にif文で判定することにした
  • できた。サンプル通った。
  • コーナーケース確認して提出。

import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class CollectingRiders {
	class State {
		int nx;
		int ny;
		int time;
		State(int x, int y, int t) {
			nx = x;
			ny = y;
			time = t;
		}
	}
	
	public int minimalMoves(String[] board) {
		int w = board[0].length();
		int h = board.length;

		int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
		int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
		int[][][][] dp = new int[h][w][h][w];
		for (int i = 0 ; i < dp.length ; i++) {
			for (int j = 0 ; j < dp[0].length ; j++) {
				for (int k = 0 ; k < dp[0][0].length ; k++) {
					Arrays.fill(dp[i][j][k], Integer.MAX_VALUE);
				}
			}
		}

		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				Queue<State> q = new ArrayBlockingQueue<State>(1000);
				q.add(new State(j, i, 0));
				dp[i][j][i][j] = 0;
				while (q.size() >= 1) {
					State stat = q.poll();
					for (int d = 0 ; d < 8 ; d++) {
						int tx = stat.nx + dx[d];
						int ty = stat.ny + dy[d];
						if (0 <= tx && tx < w && 0 <= ty && ty < h) {
							if (dp[i][j][ty][tx] > stat.time + 1) {
								dp[i][j][ty][tx] = stat.time + 1;
								q.add(new State(tx, ty, stat.time + 1));
							}
						}
					}
				}
			}
		}
		int minmove = Integer.MAX_VALUE;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				int move = 0;
				search: for (int k = 0 ; k < h ; k++) {
					for (int l = 0 ; l < w ; l++) {
						if (i == k && j == l) {
							continue;
						}
						if (board[k].charAt(l) != '.') {
							int knight = board[k].charAt(l) - '0';
							int go = dp[k][l][i][j];
							if (go == Integer.MAX_VALUE) {
								move = Integer.MAX_VALUE;
								break search;
							}
							move += (go + knight - 1) / knight;
						}
					}
				}
				minmove = Math.min(minmove, move);
			}
		}
		return (minmove == Integer.MAX_VALUE) ? -1 : minmove;
	}
}