백준 7682번: 틱택토

https://www.acmicpc.net/problem/7682

7682번: 틱택토

입력된 케이스의 o개수, x개수, 빈칸 개수, 3칸이 연결된 개수를 세서 답을 내려고 했지만,

if 처리할 경우를 모두 찾지 못했다..

 

그래서 그냥 가능한 틱택토 최종 모양을 모두 만들어서 저장한 후에 입력된 케이스가 있다면 valid, 없다면 invalid를 출력했다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[3][3];
map<string, int> m;

void make_case(int turn) {
  bool IsLastTurn = false;
  int cnt = 0;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      if (arr[i][j]) cnt++;
  if (cnt == 9) IsLastTurn = true;
  for (int i = 0; i < 3; i++) {
    if (IsLastTurn) break;
    if (arr[i][0] == 1 && arr[i][0] == arr[i][1] && arr[i][1] == arr[i][2])
      IsLastTurn = true;
    if (arr[0][i] == 1 && arr[0][i] == arr[1][i] && arr[1][i] == arr[2][i])
      IsLastTurn = true;
    if (arr[i][0] == 2 && arr[i][0] == arr[i][1] && arr[i][1] == arr[i][2])
      IsLastTurn = true;
    if (arr[0][i] == 2 && arr[0][i] == arr[1][i] && arr[1][i] == arr[2][i])
      IsLastTurn = true;
  }
  if (arr[0][0] == 1 && arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2])
    IsLastTurn = true;
  if (arr[0][2] == 1 && arr[0][2] == arr[1][1] && arr[1][1] == arr[2][0])
    IsLastTurn = true;
  if (arr[0][0] == 2 && arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2])
    IsLastTurn = true;
  if (arr[0][2] == 2 && arr[0][2] == arr[1][1] && arr[1][1] == arr[2][0])
    IsLastTurn = true;
  if (IsLastTurn) {
    string str = "";
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (arr[i][j] == 0) str += ".";
        if (arr[i][j] == 1) str += "X";
        if (arr[i][j] == 2) str += "O";
      }
    }
    m[str] = 1;
    return;
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (arr[i][j] == 0) {
        arr[i][j] = turn;
        make_case(turn == 1 ? 2 : 1);
        arr[i][j] = 0;
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      arr[i][j] = 1;
      make_case(2);
      arr[i][j] = 0;
    }
  }
  string str;
  while (true) {
    cin >> str;
    if (str == "end") break;
    if (m.find(str) == m.end())
      cout << "invalid\n";
    else
      cout << "valid\n";
  }
}