SRM588 Div2 Hard

1000

const int H = 50 + 1;
const int W = 50 + 1;
const int L = (50 + 1) * 50;
bool vis[H][W][L];

char g[H][W];
string M;
int h, w;
vector< pair<int, int> > A;

const int di[] = {0, 0, -1, +1};
const int dj[] = {-1, +1, 0, 0};

bool rec(int bi, int bj, int len)
{
  if (vis[bi][bj][len]) return false;

  int ai = A[len].first;
  int aj = A[len].second;
  if (ai == bi && aj == bj) {
    return vis[bi][bj][len] = false;
  }

  if (len == M.size()) return true;

  vis[bi][bj][len] = true;

  for (int d = 0; d < 4; ++d) {
    int ni = bi + di[d];
    int nj = bj + dj[d];
    if (ni < 0 || nj < 0) continue;
    if (h <= ni || w <= nj) continue;
    if (g[ni][nj] == '#') continue;
    if (ni == ai && nj == aj) continue;
    if (rec(ni, nj, len + 1)) return true;
  }

  return false;
}

class GameInDarknessDiv2 {
public:
  string check(vector <string> field, vector <string> moves)
  {
    h = field.size();
    w = field[0].size();
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        g[i][j] = field[i][j];
      }
    }

    M = accumulate(moves.begin(), moves.end(), string(""));

    fill(&vis[0][0][0], &vis[H - 1][W - 1][L - 1] + 1, false);

    int ai = 0, aj = 0;
    int bi = 0, bj = 0;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (g[i][j] == 'B') {
          bi = i;
          bj = j;
        }
        if (g[i][j] == 'A') {
          ai = i;
          aj = j;
        }
      }
    }

    A.clear();
    for (int i = 0; i < M.size(); ++i) {
      if (M[i] == 'U') --ai;
      if (M[i] == 'D') ++ai;
      if (M[i] == 'R') ++aj;
      if (M[i] == 'L') --aj;
      A.push_back(make_pair(ai, aj));
    }

    return rec(bi, bj, 0) ? "Bob wins" : "Alice wins";
  }