[코드트리] 루돌프의 반란 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M, P, C, D;
	static int ri, rj;
	static Santa[] santas;
	static int[][] board;

	static int[] di = { -1, 0, 1, 0, -1, 1, 1, -1 };
	static int[] dj = { 0, 1, 0, -1, 1, 1, -1, -1 };

	static class Santa {
		int number;
		int i;
		int j;
		int score;
		int sleepTurn;
		boolean alive;

		public Santa(int number, int i, int j) {
			this.number = number;
			this.i = i;
			this.j = j;
			this.score = 0;
			this.sleepTurn = -2;
			this.alive = true;
		}

		public Santa() {
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		P = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		board = new int[N][N];
		santas = new Santa[P + 1];

		st = new StringTokenizer(br.readLine());
		ri = Integer.parseInt(st.nextToken()) - 1;
		rj = Integer.parseInt(st.nextToken()) - 1;

		for (int i = 1; i < P + 1; i++) {
			st = new StringTokenizer(br.readLine());
			int number = Integer.parseInt(st.nextToken());
			int si = Integer.parseInt(st.nextToken());
			int sj = Integer.parseInt(st.nextToken());
			board[si - 1][sj - 1] = number;
			santas[number] = new Santa(number, si - 1, sj - 1);
		}

		for (int m = 0; m < M; m++) {
			if (allDied()) {
				break;
			}

			// 루돌프 이동
			moveRudol(m);

			// 산타 이동
			for (int s = 1; s < P + 1; s++) {
				Santa santa = santas[s];

				if (santa.sleepTurn + 2 > m || !santa.alive) {
					continue;
				}

				moveSanta(santa, m);
			}

			if (allDied()) {
				break;
			}

			for (int s = 1; s < P + 1; s++) {
				if (santas[s].alive) {
					santas[s].score++;
				}
			}
		}

		for (int s = 1; s < P + 1; s++) {
			System.out.print(santas[s].score + " ");
		}
	}

	private static void moveSanta(Santa santa, int turn) {
		int currentDistance = (int) (Math.pow(santa.i - ri, 2) + Math.pow(santa.j - rj, 2));
		int minDistance = currentDistance;
		int minDirection = -1;

		for (int d = 0; d < 4; d++) {
			int ni = santa.i + di[d];
			int nj = santa.j + dj[d];

			if (validate(ni, nj)) {
				if(board[ni][nj] >= 1 && board[ni][nj] <= P) continue;
				int distance = (int) (Math.pow(ni - ri, 2) + Math.pow(nj - rj, 2));

				if (distance < minDistance) {
					minDistance = distance;
					minDirection = d;
				}
			}

		}

		if (minDirection == -1 || minDistance == currentDistance) {
			return;
		}

		board[santa.i][santa.j] = 0;
		santa.i += di[minDirection];
		santa.j += dj[minDirection];

		if (santa.i == ri && santa.j == rj) {
			bombSanta(santa, minDirection, turn);
		} else {
			board[santa.i][santa.j] = santa.number;
		}
	}

	private static void bombSanta(Santa santa, int direction, int turn) {
		direction = (direction + 2) % 4;
		santa.sleepTurn = turn;
		santa.score += D;
		santa.i += di[direction] * D;
		santa.j += dj[direction] * D;

		if (!validate(santa.i, santa.j)) {
			santa.alive = false;
			return;
		}

		int number = board[santa.i][santa.j];
		if (number != 0) {
			moveChain(santas[number], direction);
		}
		board[santa.i][santa.j] = santa.number;
	}

	private static void moveRudol(int turn) {
		// 가장 가까운 산타 찾기
		Santa closeSanta = new Santa();
		int minDistance = Integer.MAX_VALUE;
		int maxI = -1;
		int maxJ = -1;
		for (int s = 1; s < P + 1; s++) {
			Santa santa = santas[s];
			if (!santa.alive)
				continue;
			int distance = (int) (Math.pow(santa.i - ri, 2) + Math.pow(santa.j - rj, 2));

			if (distance < minDistance || (distance == minDistance && santa.i > maxI)
					|| (distance == minDistance && santa.i == maxI && santa.j > maxJ)) {
				minDistance = distance;
				maxI = santa.i;
				maxJ = santa.j;
				closeSanta = santa;
			}
		}

		// 가장 가까운 산타로 가장 가까운 방향으로 이동하기
		minDistance = (int) (Math.pow(closeSanta.i - ri, 2) + Math.pow(closeSanta.j - rj, 2));
		int minDirection = -1;
		for (int d = 0; d < 8; d++) {
			int ni = ri + di[d];
			int nj = rj + dj[d];

			if (validate(ni, nj)) {
				int distance = (int) (Math.pow(closeSanta.i - ni, 2) + Math.pow(closeSanta.j - nj, 2));

				if (distance < minDistance) {
					minDistance = distance;
					minDirection = d;
				}
			}
		}

		ri += di[minDirection];
		rj += dj[minDirection];

		if (board[ri][rj] != 0) {
			bombRudol(santas[board[ri][rj]], minDirection, turn);
			board[ri][rj] = 0;
		}
	}

	private static void bombRudol(Santa santa, int direction, int turn) {
		santa.sleepTurn = turn;
		santa.score += C;
		santa.i += di[direction] * C;
		santa.j += dj[direction] * C;

		if (!validate(santa.i, santa.j)) {
			santa.alive = false;
			return;
		}

		int number = board[santa.i][santa.j];
		if (number != 0) {
			moveChain(santas[number], direction);
		}
		board[santa.i][santa.j] = santa.number;
	}

	private static void moveChain(Santa santa, int direction) {
		board[santa.i][santa.j] = 0;
		santa.i += di[direction];
		santa.j += dj[direction];

		if (!validate(santa.i, santa.j)) {
			santa.alive = false;
			return;
		}

		int number = board[santa.i][santa.j];
		if (number != 0) {
			moveChain(santas[number], direction);
		}
		board[santa.i][santa.j] = santa.number;
	}

	private static boolean validate(int ni, int nj) {
		return 0 <= ni && ni < N && 0 <= nj && nj < N;
	}

	private static boolean allDied() {
		boolean allDied = true;

		for (int s = 1; s < P + 1; s++) {
			if (santas[s].alive) {
				allDied = false;
				break;
			}
		}

		return allDied;
	}
}