## 啥？

Tic-tac-toe是我很久之前在CF上做的一道题。非常考细心的模拟题。

## show me the CODE

```class State {
public:
State(){}
int set_game(Game* igame) {
game = igame;
return 0;
}
virtual int first(int x, int y) = 0;
virtual int second(int x, int y) = 0;
virtual void show_state() = 0;
virtual ~State(){}
protected:
Game *game;
private:
State(const State&);
};
```

```class FirstState: public State {
public:
virtual int first(int x, int y);
virtual int second(int x, int y);
virtual void show_state() {
print("FirstState");
}
};

int FirstState::first(int x, int y) {
int res = game -> make_move(x, y, FIRST);
if (res == ILLEGAL) {
game -> set_state(ILLEGAL);
return ILLEGAL;
}
int next = game -> next();
switch(next) {
case SECOND:
game -> set_state(SECOND);
break;
case FIRST_WIN:
game -> set_state(FIRST_WIN);
break;
case DRAW:
game -> set_state(DRAW);
break;
default:
game -> set_state(ILLEGAL);
break;
}
return 0;
}

int FirstState::second(int x, int y) {
// P2不能操作
return ILLEGAL;
}
```

```class SecondState: public State {
public:
virtual int first(int x, int y);
virtual int second(int x, int y);

virtual void show_state() {
print("SecondState");
}
};

int SecondState::first(int x, int y) {
// P1不能操作
return ILLEGAL;
}

int SecondState::second(int x, int y) {
int res = game -> make_move(x, y, SECOND);
if (res == ILLEGAL) {
return ILLEGAL;
}

int next = game -> next();
switch(next) {
case FIRST:
game -> set_state(FIRST);
break;
case SECOND_WIN:
game -> set_state(SECOND_WIN);
break;
case DRAW:
game -> set_state(DRAW);
break;
default:
game -> set_state(ILLEGAL);
}
return 0;
}
```

```class EndState: public State {
public:
virtual int first(int x, int y) {
return ILLEGAL;
}
virtual int second(int x,int y) {
return ILLEGAL;
}
};

class FirstWinState:  public EndState {
virtual void show_state() {
print("FirstWinState");
}
};
class SecondWinState: public EndState {
virtual void show_state() {
print("SecondWinState");
}
};
class DrawState:      public EndState {
virtual void show_state() {
print("DrawState");
}
};
class IllegalState:   public EndState {
virtual void show_state() {
print("IllegalState");
}
};
```

```class Game {
public:
Game();
int set_state(int next_state);
int get_state();
int make_move(int x, int y, int player);
int next();
int first(int x, int y) {
return state_ptr -> first(x, y);
}
int second(int x, int y) {
return state_ptr -> second(x, y);
}
private:
int state;
State* state_ptr;
char board[3][3];

FirstState      firststate;
SecondState     secondstate;
FirstWinState   firstwinstate ;
SecondWinState  secondwinstate;
DrawState       drawstate;
IllegalState    illegalstate;
};

Game::Game()
{
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[i][j] = '.';
}
}
firststate    .set_game((Game*)this);
secondstate   .set_game((Game*)this);
firstwinstate .set_game((Game*)this);
secondwinstate.set_game((Game*)this);
drawstate     .set_game((Game*)this);
illegalstate  .set_game((Game*)this);

// 在开始的时候，要P1先手
set_state(FIRST);
}

int Game::set_state(int next_state)
{
state = next_state;
switch(next_state) {
case(DRAW):
state_ptr = &drawstate;
break;
case(FIRST):
state_ptr = &firststate;
break;
case(SECOND):
state_ptr = &secondstate;
break;
case(FIRST_WIN):
state_ptr = &firstwinstate;
break;
case(SECOND_WIN):
state_ptr = &secondwinstate;
break;
default:
case(ILLEGAL):
state_ptr = &illegalstate;
break;
}
return 0;
}

int Game::get_state() {
state_ptr ->show_state();
return state;
}

int Game::make_move(int x, int y, int player) {
char c;
switch(player) {
case FIRST:
c = 'X';
break;
case SECOND:
c = '0';
break;
default:
return ILLEGAL;
break;
}
if (board[y][x] != '.') {
return ILLEGAL;
}
board[y][x] = c;
return 0;
}

int Game::next() {
return judge(board);
}

// 这个函数写的太屎了，不忍直视
void check_win(char board[3][3], int& a_cnt, int& b_cnt)
{
a_cnt = b_cnt = 0;
for (int i = 0; i < 3; i++) {
char type = board[i][0];
int cnt = 0;
for (int j = 0; j < 3; j++) {
if (board[i][j] == type) {
cnt++;
} else {
break;
}
}

if (cnt == 3) {
if (type == 'X') a_cnt++;
else if (type == '0') b_cnt++;
}
}

for (int i = 0; i < 3; i++) {
char type = board[0][i];
int cnt = 0;
for (int j = 0; j < 3; j++) {
if (board[j][i] == type) {
cnt++;
} else {
break;
}
}

if (cnt == 3) {
if (type == 'X') a_cnt++;
else if (type == '0') b_cnt++;
}
}

do {
char type = board[0][0];
int cnt = 0;
for (int i = 0; i < 3; i++) {
if (board[i][i] == type) {
cnt++;
} else {
break;
}
}
if (cnt == 3) {
if (type == 'X') a_cnt++;
else if (type == '0') b_cnt++;
}
} while(0);

do {
char type = board[0][2];
int cnt = 0;
for (int i = 0; i < 3; i++) {
if (board[2 - i][i] == type) {
cnt++;
} else {
break;
}
}
if (cnt == 3) {
if (type == 'X') a_cnt++;
else if (type == '0') b_cnt++;
}
} while(0);
}

// 同上。。。模拟题就是那么恶心。。。_(:з」∠)_
// 也许我会有机会重构一下。。。
int judge(char board[3][3])
{
int next = -1;
int a_cnt = 0, b_cnt = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 'X') a_cnt++;
else if (board[i][j] == '0') b_cnt++;
}
}
if (a_cnt < b_cnt || a_cnt - b_cnt > 1) {
return ILLEGAL;
}

if (a_cnt + b_cnt == 9) {
// PASS
} else if (a_cnt == b_cnt) {
next = 1;
} else {
next = 2;
}

a_cnt = b_cnt = 0;
check_win(board, a_cnt, b_cnt);

if (a_cnt == 0 && b_cnt == 0) {
//nobody wins and the board is full
switch(next) {
case -1:
return DRAW;
case 1:
return FIRST;
case 2:
return SECOND;
}
} else if (b_cnt && a_cnt) {
return ILLEGAL;
} else if (b_cnt && !a_cnt) {
if (next == 2) {
return ILLEGAL;
} else {
return SECOND_WIN;
}
} else if (a_cnt && !b_cnt) {
if (next == 1) {
return ILLEGAL;
} else {
return FIRST_WIN;
}
} else {
// NO ELSE HERE;
}

return next == 1? FIRST : SECOND;
}
```

```const int ILLEGAL = -1;
const int DRAW = 0;
const int FIRST = 1;
const int SECOND = 2;
const int FIRST_WIN = 100;
const int SECOND_WIN = 200;
```

## how it works

`class Game`中的`state_ptr`指针标示了当然自动机的状态。从`class Game`调用`first``second`函数的行为被委托给了当前的`State`，产生了不同的动作。

## 为什么要这么写

（p.s. DSL我了解不多，如果理解有偏差，请谅解）