[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関数が使用する点火式の考え方は ソースコード(JAVA)
アルゴリズムトラブルシューティングポリシー-ダイナミックプランニング
https://algospot.com/judge/problem/read/TICTACTOE
問題を解く
これは
현재 보드에 turn말을 놓았을 때 다음 canWin(변화된 보드, 상대방말)이 지는 경우(turn말이 이기는 경우)가 있을 경우 1(turn말이 이기는 경우)을 리턴
である.(詳細については、コードを参照)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;
}
}
Reference
この問題について([AlgoSpot]チェックマーク), 我々は、より多くの情報をここで見つけました https://velog.io/@ddongh1122/AlgoSpot-틱택토テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol