Solution to Board Game (gam)

gam.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>

using namespace std;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int N;
string A[310];

int D1[310*310];
int D2[310*310];

/* Find the distance from position (r, c) to all other positions and store it in
 * D.  D is indexed in row-major order. */
void bfs(int r, int c, int N, int* D) {
  memset(D, 0x1F, sizeof(int) * N * N);
  queue<int> q;
  q.push(r * N + c);
  D[r * N + c] = 0;

  /* Do a standard BFS.  This code is very standard and is worth knowing. */
  while(!q.empty()) {
    /* Note the unpacking pattern, v -> (vr, vc) */
    int v = q.front(); q.pop();
    int vr = v / N;
    int vc = v % N;
    int nd = D[v] + 1;
    for(int i = 0; i < 4; i++) {
      /* And the reverse packing pattern, (nr, nc) -> nv */
      int nr = vr + dr[i];
      int nc = vc + dc[i];
      int nv = nr * N + nc;
      if(nr < 0 || nr >= N || nc < 0 || nc >= N ||
         A[nr][nc] == '#' || D[nv] <= nd) continue;

      D[nv] = nd;
      q.push(nv);
    }
  }
}

int ID[310*310];

char memo[310*310][310];

/* The moving player is at (r1, c1) and the other player is at (r2, c2).
 * d1 and d2 give the distances from the starting cell of the moving player and
 * other player (respectively) to every other cell (in row major order).
 * Returns true if the leading player can win. */
bool search(int r1, int c1, int r2, int c2, int* d1, int* d2) {
  int v1 = r1 * N + c1;
  int v2 = r2 * N + c2;

  /* When the players arrive at the midpoint, player A wins iff they occupy
   * different cells.  Otherwise player B would have gotten to move again and
   * therefore would win. */
  if(d1[v1] == d2[v1]) return v1 != v2;

  /* Lookup this state in the cache.  If we've solved it already, return that.
   */
  char& ref = memo[v1][ID[v2]];
  if(ref != -1) return ref;

  /* Try moving from this cell.  We must stay on a shortest path to the opposite
   * starting cell or the opponent will win. */
  for(int i = 0; i < 4; i++) {
    int nr = r1 + dr[i];
    int nc = c1 + dc[i];
    int nv = nr * N + nc;
    if(nr < 0 || nr >= N || nc < 0 || nc >= N ||
       A[nr][nc] == '#' || d2[nv] != d2[v1] - 1) continue;

    /* The leading player can win if it can make a move that causes the other
     * player to lose. */
    if(!search(r2, c2, nr, nc, d2, d1)) {
      return ref = true;
    }
  }
  return ref = false;
}

int main() {
  int T; cin >> T;
  for(int t = 1; t <= T; t++) {
    cin >> N;
    for(int i = 0; i < N; i++) {
      cin >> A[i];
    }

    /* Find the start cells of each player. */
    int r1 = -1, c1 = -1, r2 = -1, c2 = -1;
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(A[i][j] == 'A') {
          r1 = i; c1 = j;
        } else if(A[i][j] == 'B') {
          r2 = i; c2 = j;
        }
      }
    }

    /* If the distance between starting points is odd then A will win. */
    if((r1 + c1 + r2 + c2) % 2 == 1) {
      cout << "A" << endl;
      continue;
    }

    /* Compute the shortest path from each starting cell to all other cells. */
    bfs(r1, c1, N, D1);
    bfs(r2, c2, N, D2);

    /* This is a trick to make the memoization more efficient.  For each
     * position of the currently moving player the distance of the other player
     * from each of the starting cells is fixed.  Therefore we can index are
     * memo array this way.  This is cheaper than using a map which will cause
     * this solution to time out. */
    int dst = D1[r2 * N + c2];
    memset(ID, -1, sizeof(ID));
    vector<int> nid(dst + 1, 0);
    for(int i = 0; i < N * N; i++) {
      if(D1[i] + D2[i] == dst) {
        ID[i] = nid[D1[i]]++;
      }
    }
    for(int i = 0; i < N * N; i++) {
      for(int j = 0; j < N; j++) {
        memo[i][j] = -1;
      }
    }

    cout << (search(r1, c1, r2, c2, D1, D2) ? "A" : "B") << endl;
  }
}