[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;
        }
    }