bool isFull(vector &board)
{
for(int y = 0; y < 3; ++y)
{
for(int x = 0; x < 3; ++x) {
if(board[y][x] == '.')
return false;
}
}
return true;
}
// turn 이 한 줄을 만들었는지를 반환한다
bool isFinished(const vector& board, char turn) {
int count = 0;
//가로줄 확인
for(int y = 0; y < 3; ++y)
{
count =0 ;
for(int x = 0; x < 3; ++x) {
if(board[y][x] == turn)
count++;
}
if(count==3)
return true;
}
//세로줄 확인
for(int x = 0; x < 3; ++x)
{
count =0 ;
for(int y = 0; y < 3; ++y) {
if(board[y][x] == turn)
count++;
}
if(count==3)
return true;
}
//대각선 2개 확인
if( board[0][0] == turn && board[1][1] == turn && board[2][2] == turn )
return true;
if( board[0][2] == turn && board[1][1] == turn && board[2][0] == turn )
return true;
return false;
}
// 틱택토 게임판이 주어질 때 [0,19682] 범위의 정수로 변환한다
int bijection(const vector& board) {
int ret = 0;
for(int y = 0; y < 3; ++y)
for(int x = 0; x < 3; x++) {
ret = ret * 3;
if(board[y][x] == 'o') ++ret;
else if(board[y][x] == 'x') ret += 2;
}
return ret;
}
//판단 할 때에는 최선을 다한다는 것은 이기는것(0) < 비기는것(1) < 지는것(2) 이 되어야 한다.
//각 턴마다 이기는 플레이어를 구분해야 하므로
// x 턴일 경우 0<1<2 가 되고 min
// o 턴일 경우 2>1>0 이 되어야 한다. max
int canWin(vector& board, char turn) {
// 기저 사례: 마지막에 상대가 둬서 한줄이 만들어진 경우
//마지막 수로 끝이 나면 이긴 것이므로
if(isFinished(board, 'o'+'x'-turn))
{
//승리한 플레이의의 값을 리턴한다.
if('o'+'x'-turn == 'x')
return 0;
else
return 2;
}
int& ret = cache[bijection(board)];
if(ret != -1)
return ret;
int rValue = 1;
for(int y = 0; y < 3; ++y)
for(int x = 0; x < 3; ++x) {
if(board[y][x] == '.') {
board[y][x] = turn;
if(turn == 'x')
rValue = min(rValue, canWin(board, 'o'+'x'-turn));
else
rValue = max(rValue, canWin(board, 'o'+'x'-turn));
board[y][x] = '.';
}
}
// 플레이할수 없거나, 어떻게 해도 비기는 것이 최선인 경우
if(rValue == 3 || rValue == 1) return ret = 1;
// 어떻게 해도 지는 경우
return ret = rValue;
}
int main()
{
int C;
freopen("D:\\MyProject\\CodeJam\\연습\\SampleCode\\a.in","r",stdin);
scanf("%d", &C);
while(C-->0)
{
vector<string> bd;
bd.clear();
memset(cache, -1, MAX_CACHE);
for(int i=0; i<3; i++)
{
char temp[4];
scanf ("%s", &temp);
bd.push_back(temp);
}
int val;
bool valo, valx;
char turn = getturn(bd);
valo= isFinished(bd, 'o');
valx= isFinished(bd, 'x');
if(!valo && !valx)
{
//이함수의 내용은 즉 최선을 다해 이겼거나 또는 비긴 경우만을 리턴하며
//최선을 다해 이겻을 때 들어간 turn 이 승자가 되어 처리가 된다.
val = canWin(bd, turn);
}else if(valo && valx)
{
val = 1;
}else if(valo)
val = 2;
else
val= 0;
if(val==1)
printf("TIE\n");
else if(val==0)
printf("x\n");
else
printf("o\n");
}
return 0;
qwoowp
알고에 있는 미완성 소스로 제가 이해하는데로
코드를 짜보았는데요.
어떤 케이스에서 실패가 되는지 모르겟어요..
코드가 계속 덧붙이다 보니 어지럽기도 하고 ㅠ.ㅠ;;;
조언좀 부탁드려요..
#pragma warning(disable:4996)
#include
#include
#include
#include
#include
#include
using namespace std;
//2비트씩 9개 이므로 18bit 를 사용한다.
#define MAX_CACHE (1<<18)
int cache[MAX_CACHE];
int board;
//초기 보드 상태를 받아서 현재 진행할 차례가 누구인지 알려준다. bd)
//0 : x
//1 : o
char getturn(vector
{
int x_count= 0;
int o_count=0;
}
bool isFull(vector &board)
{
for(int y = 0; y < 3; ++y)
{
for(int x = 0; x < 3; ++x) {
if(board[y][x] == '.')
return false;
}
}
return true;
}
// turn 이 한 줄을 만들었는지를 반환한다& board, char turn) {
bool isFinished(const vector
int count = 0;
//가로줄 확인
for(int y = 0; y < 3; ++y)
{
count =0 ;
for(int x = 0; x < 3; ++x) {
if(board[y][x] == turn)
count++;
}
if(count==3)
return true;
}
}
// 틱택토 게임판이 주어질 때 [0,19682] 범위의 정수로 변환한다& board) {
int bijection(const vector
int ret = 0;
for(int y = 0; y < 3; ++y)
for(int x = 0; x < 3; x++) {
ret = ret * 3;
if(board[y][x] == 'o') ++ret;
else if(board[y][x] == 'x') ret += 2;
}
return ret;
}
//판단 할 때에는 최선을 다한다는 것은 이기는것(0) < 비기는것(1) < 지는것(2) 이 되어야 한다.& board, char turn) {
//각 턴마다 이기는 플레이어를 구분해야 하므로
// x 턴일 경우 0<1<2 가 되고 min
// o 턴일 경우 2>1>0 이 되어야 한다. max
int canWin(vector
// 기저 사례: 마지막에 상대가 둬서 한줄이 만들어진 경우
//마지막 수로 끝이 나면 이긴 것이므로
if(isFinished(board, 'o'+'x'-turn))
{
//승리한 플레이의의 값을 리턴한다.
if('o'+'x'-turn == 'x')
return 0;
else
return 2;
}
}
int main()
{
int C;
}
10년 전