AtCoder Beginner Contest 025 C: 双子と○×ゲーム

問題

abc025.contest.atcoder.jp

解法

AtCoder Beginner Contest 025 解説 from AtCoder Inc.

www.slideshare.net

コード

import java.util.Scanner;

public class Main {
	private int[][] b;
	private int[][] c;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int sum = 0;
		b = new int[2][3];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				b[i][j] = scanner.nextInt();
				sum += b[i][j];
			}
		}
		c = new int[3][2];
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 2; j++) {
				c[i][j] = scanner.nextInt();
				sum += c[i][j];
			}
		}
		scanner.close();

		int chokudai = minmaxDFS(new int[3][3], 0);
		System.out.println(chokudai);
		System.out.println(sum - chokudai);
	}

	private int minmaxDFS(int[][] board, int turn) {
		// 先手の点数を返す
		if (turn == 9) {
			return score(board);
		}

		// 先手の時は最大値、後手の時は最小値を返す
		int minmax = turn % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (board[i][j] != 0) {
					continue;
				}
				if (turn % 2 == 0) {
					// 先手
					board[i][j] = 1;
					minmax = Math.max(minmax, minmaxDFS(board, turn + 1));
					board[i][j] = 0;
				} else {
					// 後手
					board[i][j] = 2;
					minmax = Math.min(minmax, minmaxDFS(board, turn + 1));
					board[i][j] = 0;
				}
			}
		}
		return minmax;
	}

	private int score(int[][] board) {
		int score = 0;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				if (board[i][j] == board[i + 1][j]) {
					score += b[i][j];
				}
			}
		}
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 2; j++) {
				if (board[i][j] == board[i][j + 1]) {
					score += c[i][j];
				}
			}
		}
		return score;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}