PKU : 3075 - Tic-Tac-Toe

実装問題

問題概要

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

三目並べにおいて, Xが先手だとすると, 盤面の終了時の状態として合っているか判定する問題.

アルゴリズム

PKU 2361の条件にちょっと付け加えてやるだけで解ける.
次の条件のいずれかを満たすときNOと言える.

  • Xの数 != Oの数 かつ Xの数 != Oの数+1
  • XとOが両方ともそろっている
  • Xの数 != 5 でかつ, Oの数 != 4 でかつ, XもOもそろっていない
  • Xの数 == Oの数のとき, Xがそろってしまっている
  • Xの数 == Oの数+1のとき, Oがそろってしまっている

プログラム

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--){
    char s[10];
    scanf("%s",s);
    if(s[0] == 'e') break;

    int X=0,O=0;
    rep(i,3){
      strncpy(t[i],&s[i*3],3);
      rep(j,3){
        if(t[i][j] == 'O') O++;
        else if(t[i][j] == 'X') X++;
      }
    }

    bool Xwin = win('X');
    bool Owin = win('O');
    if(X != O && X != O+1 || Xwin && Owin ||
       X != 5 && O != 4 && !Xwin && !Owin ||
       X == O && Xwin || X == O+1 && Owin){
      printf("invalid\n");
    }
    else{
      printf("valid\n");
    }
  }
}