[코드트리] 고대 문명 유적 탐사 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int K, M;
	static int[][] board;
	static int[] bomul;
	static int totalValue;
	static int currentM = 0;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[5][5];
		bomul = new int[M];

		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < 5; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			bomul[i] = Integer.parseInt(st.nextToken());
		}

		for (int k = 0; k < K; k++) {
			Result result = new Result(0, new int[5][5]);
			int maxValue = -1;
			int bestD = -1;
			int bestJ = -1;
			int[][] turnBoard = new int[5][5];

			for (int d = 1; d <= 3; d++) {
				for (int j = 0; j < 3; j++) {
					for (int i = 0; i < 3; i++) {
						result = calculateValue(i, j, d);

						if (result.value > maxValue) {
							maxValue = result.value;
							turnBoard = result.turnBoard;
						}
					}
				}
			}

			if (maxValue <= 0) {
				return;
			}

			getValue(turnBoard);
			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					board[i][j] = turnBoard[i][j];
				}
			}
			System.out.print(totalValue + " ");
		}
	}

	private static void getValue(int[][] board) {
		totalValue = 0;

		boolean[][] visited;
		boolean changed;
		ArrayList<int[]> valuePos = new ArrayList<>();

		while (true) {
			changed = false;
			visited = new boolean[5][5];

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					if (!visited[i][j]) {
						valuePos = bfs(i, j, board, visited);

						if (valuePos != null) {
							totalValue += valuePos.size();
							changed = true;

							for (int[] pos : valuePos) {
								board[pos[0]][pos[1]] = 0;
							}
						}
					}
				}
			}

			if (!changed)
				break;
			offerValue(board);
		}
	}

	private static void offerValue(int[][] board) {
		for (int j = 0; j < 5; j++) {
			for (int i = 4; i >= 0; i--) {
				if (board[i][j] == 0) {
					board[i][j] = bomul[currentM++];
				}
			}
		}
	}

	private static Result calculateValue(int si, int sj, int dir) {
		int[][] turn = new int[5][5];
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				turn[i][j] = board[i][j];
			}
		}

		for (int d = 0; d < dir; d++) {
			int[][] copy = new int[3][3];

			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					copy[i][j] = turn[si + i][sj + j];
				}
			}
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					turn[si + j][sj + 2 - i] = copy[i][j];
				}
			}
		}

		int value = 0;
		boolean[][] visited = new boolean[5][5];
		ArrayList<int[]> valuePos = new ArrayList<>();

		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if (!visited[i][j]) {
					valuePos = bfs(i, j, turn, visited);

					if (valuePos != null) {
						value += valuePos.size();
					}
				}
			}
		}

		return new Result(value, turn);
	}

	private static ArrayList<int[]> bfs(int si, int sj, int[][] board, boolean[][] visited) {
		ArrayDeque<int[]> dq = new ArrayDeque<>();
		ArrayList<int[]> valuePos = new ArrayList<>();
		int number = board[si][sj];

		valuePos.add(new int[] { si, sj });
		dq.add(new int[] { si, sj });
		visited[si][sj] = true;

		while (!dq.isEmpty()) {
			int[] current = dq.poll();
			int ci = current[0];
			int cj = current[1];

			for (int d = 0; d < 4; d++) {
				int ni = ci + di[d];
				int nj = cj + dj[d];

				if (validate(ni, nj) && !visited[ni][nj]) {
					if (board[ni][nj] == number) {
						dq.add(new int[] { ni, nj });
						visited[ni][nj] = true;
						valuePos.add(new int[] { ni, nj });
					}
				}
			}
		}

		if (valuePos.size() >= 3) {
			return valuePos;
		}
		return null;
	}

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

	static class Result {
		int value;
		int[][] turnBoard;

		public Result(int value, int[][] turnBoard) {
			this.value = value;
			this.turnBoard = turnBoard;
		}
	}
}