SRM 156 DIV-1 1000 Path Finding

Problem Statement

class PathFinding {
public:
  int minTurns(vector <string> board) {
    typedef struct state {
      int ax, ay, bx, by;
      int step;
    } state;

    state s;
    s.ax = s.ay = s.bx = s.by = -1;
    bool visited[20][20][20][20] = {false};
    int rows = board.size(), cols = board[0].size();

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (board[i][j] == 'A') {
          s.ax = i; s.ay = j;
        }
        if (board[i][j] == 'B') {
          s.bx = i; s.by = j;
        }
      }
    }

    // Invalid board in first place.
    if (s.ax == -1 || s.bx == -1) return -1;
    s.step = 0;

    queue<state> q;
    q.push(s);
    visited[s.ax][s.ay][s.bx][s.by] = true;
    while (!q.empty()) {
      state node = q.front();
      q.pop();
      if (node.ax == s.bx && node.ay == s.by && node.bx == s.ax &&
          node.by == s.ay) {
        return node.step;
      }

      for (int dx1 = -1; dx1 <= 1; ++dx1) {
        for (int dy1 = -1; dy1 <= 1; ++dy1) {
          for (int dx2 = -1; dx2 <= 1; ++dx2) {
            for (int dy2 = -1; dy2 <= 1; ++dy2) {
              int axx = node.ax + dx1;
              int ayy = node.ay + dy1;
              int bxx = node.bx + dx2;
              int byy = node.by + dy2;

              // Out of board.
              if (axx < 0 || axx >= rows || ayy < 0 || ayy >= cols ||
                  bxx < 0 || bxx >= rows || byy < 0 || byy >= cols) {
                continue;
              }

              if (board[axx][ayy] == 'X' || board[bxx][byy] == 'X') {
                continue; // obstacle.
              }

              // Crossed line (both moves)
              if (axx == node.bx && ayy == node.by && bxx == node.ax && byy == node.ay) {
                continue;
              }
              // Cross line (a single side move)
              if (axx == bxx && ayy == byy) continue;

              if (visited[axx][ayy][bxx][byy]) continue;
              state ns;
              ns.step = node.step + 1;
              ns.ax = axx, ns.ay = ayy, ns.bx = bxx, ns.by = byy;
              visited[axx][ayy][bxx][byy] = true;
              q.push(ns);
            }
          }
        }
      }
    }

    return -1;
  }
};