[AlgoSpot]チェックマーク

問題の説明
アルゴリズムトラブルシューティングポリシー-ダイナミックプランニング
https://algospot.com/judge/problem/read/TICTACTOE
問題を解く
これは

動的計画法の問題です.

プールで使用されるユーティリティとメイン関数は次のとおりです.

char isFinish(char[]]map):現在の碁盤状態では、勝った駒の形状が回復し、勝った駒が勝っていない駒は、

に戻る

int createCacheIndex(文字[]])map):現在の基板をキャッシュアレイインデックス

に変換する.

int canWin(char[][]map,charturn):車に戻るときに1に勝って、0に引き分けて、1に負けます.

では、createCacheIndexはキャッシュのインデックスに使用され、ボード上の各セルの状態を3つに分けるために使用されます(o、x、.)基板を3進数の関数に設定します.

ビット関数の中で最も重要なcanwin関数が使用する点火式の考え方は현재 보드에 turn말을 놓았을 때 다음 canWin(변화된 보드, 상대방말)이 지는 경우(turn말이 이기는 경우)가 있을 경우 1(turn말이 이기는 경우)을 리턴である.(詳細については、コードを参照)

ソースコード(JAVA)

import java.util.Scanner;

public class Main {
    public static int C;
    public static char[][] map = new char[3][3];
    public static int[] cache = new int[19684];
    //어떤 말이던 이기는 상태일 경우 이기는 말 리턴
    //아니면 'n' 리턴
    public static char isFinished(char[][] map) {
        //가로
        for (int i = 0; i < 3; i++) {
            if (map[i][0] != '.' && map[i][1] == map[i][0] && map[i][2] == map[i][0])
                return map[i][0];
        }
        //세로
        for (int i = 0; i < 3; i++) {
            if (map[0][i] != '.' && map[1][i] == map[0][i] && map[2][i] == map[0][i])
                return map[0][i];
        }
        //대각선
        if (map[0][0] != '.' && map[1][1] == map[0][0] && map[2][2] == map[0][0]) return map[0][0];
        if (map[2][0] != '.' && map[1][1] == map[2][0] && map[0][2] == map[2][0]) return map[2][0];
        return 'n';
    }

    //현재 map 상태로 cache를 만듬
    //'.' : 0, 'X' : 1, 'O' : 2
    public static int createCacheIndex(char[][] map) {
        int ret = 0; //총 값
        int num = 1; //자리수
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (map[i][j] == 'x') ret += (num * 1);
                else if (map[i][j] == 'o') ret += (num * 2);
                num *= 3;
            }
        }
        return ret;
    }

    //turn이라는 말을 놓았을때
    //turn이 이기면 1
    //비기면 0
    //turn이 지면 -1 리턴
    public static int canWin(char[][] map, char turn) {
        //기저 사례
        char res = isFinished(map);
        if (res != 'n') {
            if (res == turn) return 1;
            else return -1;
        }
        //다이나믹 프로그래밍
        int cacheIndex = createCacheIndex(map);
        if (cache[cacheIndex] != -2) return cache[cacheIndex];

        int minValue = 2;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (map[i][j] == '.') {
                    map[i][j] = turn;
                    minValue = Math.min(minValue, canWin(map, turn == 'o' ? 'x' : 'o'));
                    map[i][j] = '.';
                }
            }
        }

        if (minValue == 2 || minValue == 0) cache[cacheIndex] = 0;
        else cache[cacheIndex] = -minValue;
        return cache[cacheIndex];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            for (int i = 0; i < 3; i++) {
                String tmp = sc.next();
                map[i] = tmp.toCharArray();
            }
            //초기화
            for (int i = 0; i < 19684; i++)
                cache[i] = -2;
            //누구 턴인지 찾기
            int aCnt = 0;
            int bCnt = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (map[i][j] == 'x') aCnt++;
                    if (map[i][j] == 'o') bCnt++;
                }
            }
            int result;
            if (aCnt > bCnt) result = canWin(map, 'o');
            else result = canWin(map, 'x');

            if (result == -1) System.out.println(aCnt > bCnt ? 'x' : 'o');
            else if (result == 0) System.out.println("TIE");
            else System.out.println(aCnt > bCnt ? 'o' : 'x');
        }
        return;
    }
}