UVa 10536 - Game of Euler

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class Key, class Compare = less<Key>> // find_by_order, order_of_key (for multiset: pair(val, time of insertion))
using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;




int dp[4][1<<16];

int step(int p, int m) {
  if (dp[p][m] != -1) {
    return dp[p][m];
  }
  if (m == (1 << 16) - 1) {
    return dp[p][m] = 1;
  }
  // perpendicular to board
  for (int i = 0; i < 16; ++i) {
    if ((m & (1 << i)) == 0) {
      int m1 = m | (1 << i);
      for (int d = 0; d < 3; ++d) {
        if (d != p && step(d, m1) == 0) {
          return dp[p][m] = 1;
        }
      }
    }
  }
  // from left
  for (int i = 0; i < 16; i += 4) {
    int m1 = m;
    for (int d = 0; d < 3; ++d) {
      int j = i + d;
      if ((m & (1 << j)) == 0) {
        m1 |= (1 << j);
        if (d != p && step(d, m1) == 0) {
          return dp[p][m] = 1;
        }
      } else {
        break;
      }
    }
  }
  // from right
  for (int i = 3; i < 16; i += 4) {
    int m1 = m;
    for (int d = 0; d < 3; ++d) {
      int j = i - d;
      if ((m & (1 << j)) == 0) {
        m1 |= (1 << j);
        if (d != p && step(d, m1) == 0) {
          return dp[p][m] = 1;
        }
      } else {
        break;
      }
    }
  }
  // from top
  for (int i = 0; i < 4; ++i) {
    int m1 = m;
    for (int d = 0; d < 3; ++d) {
      int j = i + 4*d;
      if ((m & (1 << j)) == 0) {
        m1 |= (1 << j);
        if (d != p && step(d, m1)) {
          return dp[p][m] = 1;
        }
      } else {
        break;
      }
    }
  }
  // from bottom
  for (int i = 12; i < 16; ++i) {
    int m1 = m;
    for (int d = 0; d < 3; ++d) {
      int j = i - 4*d;
      if ((m & (1 << j)) == 0) {
        m1 |= (1 << j);
        if (d != p && step(d, m1)) {
          return dp[p][m] = 1;
        }
      } else {
        break;
      }
    }
  }
  return dp[p][m] = 0;
}

void Solution() {
  memset(dp, -1, sizeof(dp));
  int T;
  cin >> T;
  while (T--) {
    int m = 0;
    for (int i = 0; i < 16; ++i) {
      char ch;
      cin >> ch;
      if (ch == 'X') {
        m |= (1 << i);
      }
    }
    int res = 0;
    for (int p = 0; p < 3; ++p) {
      res = step(p, m);
      if (res == 1) break;
    }
    cout << (res ? "WINNING\n" : "LOSING\n");
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef _DEBUG
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  #endif
  Solution();
}