PKU : 2361 - Tic Tac Toe

実装問題

問題概要

http://poj.org/problem?id=2361

三目並べ（Tic Tac Toe）をXのターンから始めたとき, 入力の盤面が途中経過or終了時の盤面として正しいかどうかを判定せよ.

アルゴリズム

次のいずれかの条件を満たしてしまうときはNOと言えます

  • Xの数 != Oの数 かつ Xの数 != Oの数+1
  • XとOが両方ともそろっている
  • Xの数 == Oの数のとき, Xがそろってしまっている
    • これを満たすと, Xが揃えたあとにOが書いたことになってしまう
  • Xの数 == Oの数+1のとき, Oがそろってしまっている
    • Oが揃えたあとに, Xが書いてしまったことになる

プログラム

char t[4][4];

bool win(char ch){
  int d1 = 0, d2 = 0;

  rep(i,3){
    int row = 0, col = 0;
    rep(j,3){
      row += (t[i][j] == ch);
      col += (t[j][i] == ch);
    }
    if(row == 3 || col == 3) return true;

    d1 += (t[i][i] == ch);
    d2 += (t[i][2-i] == ch);
  }
  return d1 == 3 || d2 == 3;
}

int main(void){
  int T;
  scanf("%d",&T);

  while(T--){
    int X=0,O=0;
    rep(i,3){
      scanf("%s",t[i]);
      rep(j,3){
        if(t[i][j] == 'O') O++;
        else if(t[i][j] == 'X') X++;
      }
    }

    if(X != O && X != O+1 || win('X') && win('O') ||
       X == O && win('X') || X == O+1 && win('O')){
      printf("no\n");
    }
    else{
      printf("yes\n");
    }
  }
}