2013年2月28日

UVa 10363 - Tic Tac Toe


#include <cstdio>
#include <string>
#include <queue>
#include <set>
#define MP make_pair
using namespace std;

typedef pair<string, bool> P;

bool win(string s) {
  int r, c;
  for (r = 0; r < 3; r++)
    if (s[r * 3] != '.' && s[r * 3] == s[r * 3 + 1] && s[r * 3 + 1] == s[r * 3 + 2]) return 1;
  for (c = 0; c < 3; c++)
    if (s[c] != '.' && s[c] == s[c + 3] && s[c + 3] == s[c + 6]) return 1;
  if (s[0] != '.' && s[0] == s[4] && s[4] == s[8]) return 1;
  if (s[2] != '.' && s[2] == s[4] && s[4] == s[6]) return 1;
  return 0;
}

int main() {
  string s(".........");
  set<string> dic;
  queue<P> q;
  dic.insert(s);
  q.push(MP(s, 0));
  while (!q.empty()) {
    string now = q.front().first;
    bool turn = q.front().second;
    q.pop();
    if (win(now)) {
      dic.insert(now);
      continue;
    }
    int i;
    for (i = 0; i < 9; i++) {
      string next(now);
      if (next[i] == '.') {
        next[i] = turn ? 'O' : 'X';
        if (!dic.count(next)) {
          q.push(MP(next, !turn));
          dic.insert(next);
        }
      }
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    char s1[10], s2[10], s3[10];
    scanf("%s%s%s", s1, s2, s3);
    puts(dic.count(string(s1) + s2 + s3) ? "yes" : "no");
  }
  return 0;
}

沒有留言:

張貼留言