Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2010-09-27SRM382 DIV1

SRM382 DIV1 easy

| 09:05

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

import java.util.Arrays;

// 84.58 pt.
public class CollectingRiders {
	private int[][] powers;

	public int minimalMoves(String[] board) {
		powers = new int[board.length][board[0].length()];
		int[][] turns = new int[board.length][board[0].length()];

		int y = 0;
		for (String line : board) {
			int x = 0;
			for (char cell : line.toCharArray()) {
				if (Character.isDigit(cell)) {
					int[][] turnsFromCell = createArray(turns, Integer.MAX_VALUE);
					turnsFromCell[y][x] = 0;
					markNext(turnsFromCell, x, y, cell - '0', 1, cell - '0');
					add(turns, turnsFromCell);
				}
				++x;
			}
			++y;
		}

		return minOf(turns);
	}
	
	private int minOf(int[][] turns) {
		int result = Integer.MAX_VALUE;
		for (int[] a : turns) {
			for (int b : a) {
				result = Math.min(result, b);
			}
		}

		return result == Integer.MAX_VALUE ? -1 : result;
	}

	private void add(int[][] turns, int[][] turnsFromCell) {
		for (int i = 0; i < turns.length; ++i) {
			for (int j = 0; j < turns[0].length; ++j) {
				if (turnsFromCell[i][j] == Integer.MAX_VALUE) {
					turns[i][j] = Integer.MAX_VALUE;
				} else if (turns[i][j] != Integer.MAX_VALUE) {
					turns[i][j] += turnsFromCell[i][j];
				}
			}
		}
	}

	private static final int[] JUMP_X = new int[] {-1, 1, 2, 2, 1,-1,-2,-2};
	private static final int[] JUMP_Y = new int[] {-2,-2,-1, 1, 2, 2, 1,-1};

	private void markNext(int[][] a, int x, int y, int power, int turn, int maxPower) {
		if (turn == 10) return;

		for (int i = 0; i < JUMP_X.length; ++i) {
			int jumpX = x + JUMP_X[i];
			int jumpY = y + JUMP_Y[i];

			if (jumpX < 0 || jumpY < 0 || a.length <= jumpY || a[0].length <= jumpX) {
				continue;
			} else if (a[jumpY][jumpX] == turn) {
				if (power > 1 && powers[jumpY][jumpX] < power) {
					powers[jumpY][jumpX] = power;
					markNext(a, jumpX, jumpY, power - 1, turn, maxPower);
				}
			} else if (a[jumpY][jumpX] >= turn) {
				a[jumpY][jumpX] = turn;
				powers[jumpY][jumpX] = power;
				if (power > 1) {
					markNext(a, jumpX, jumpY, power - 1, turn, maxPower);
				}
				markNext(a, jumpX, jumpY, maxPower, turn + 1, maxPower);
			}
		}
	}

	private int[][] createArray(int[][] source, int defaultValue) {
		int[][] result = new int[source.length][source[0].length];
		for (int[] a : result) {
			Arrays.fill(a, defaultValue);
		}
		return result;
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		CollectingRiders temp = new CollectingRiders();
		System.out.println(temp.minimalMoves(new String[] {"1.", "..", "..", "..", "..", "1."}));
	}
// END CUT HERE
}