Solution to SPOJ's QUEEN

queen.cpp

#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

#include <string>
#include <cstring>
#include <cctype>
#include <cstdio>

#include <cassert>

struct IO {
  IO(FILE* fin) {
    struct stat buf;
    int fd = fileno(fin);
    fstat(fd, &buf);
    sin = (char*)mmap(NULL, (buf.st_size + 1023) & ~1023,
                      PROT_READ, MAP_PRIVATE, fd, 0);
  }

  ~IO() {
  }

  void skip_space() {
    while(isspace(*sin)) {
      ++sin;
    }
  }

  template<class T>
  T read_integer() {
    bool neg = *sin == '-';
    if(neg) ++sin;

    T r = 0;
    while('0' <= *sin && *sin <= '9') {
      r *= 10;
      r += *sin++ - '0';
    }
    return neg ? -r : r;
  }

  std::string read_string() {
    char* s = sin;
    while(!isspace(*sin)) ++sin;
    return std::string(s, sin);
  }

  void read_string(char* out) {
    char* s = sin;
    while(!isspace(*sin)) ++sin;
    memcpy(out, s, sin - s);
    out[sin - s] = 0;
  }

  void skip_amount(int amt) {
    sin += amt;
  }

  char* sin;
};

int Q[1000010];
int D[1 << 20];

int N;
int M;

inline int arr(int r, int c) {
  //return r * 1024 + c;
  //return c * N + r;
  return r * M + c;
}

inline int& darr(int r, int c) {
  return D[arr(r, c)];
  //return D[s16(r) | s16(c) << 1];
  //return D[c * N + r];
  //return D[r * M + c];
}

inline int& darrv(int v) {
  return D[v];
  //return darr(v / M, v % M);
}

int main() {
  IO io(stdin);

  io.skip_space();
  int T = io.read_integer<int>();
  for(int t = 1; t <= T; t++) {
    io.skip_space();
    N = io.read_integer<int>();
    io.skip_space();
    M = io.read_integer<int>();
    N += 2;
    M += 2;

    int ss = -1, tt = -1;
    for(int j = 0; j < M; j++) {
      darr(0, j) = -2;
      darr(N - 1, j) = -2;
    }
    for(int i = 1; i + 1 < N; i++) {
      io.skip_space();
      char* base = io.sin - 1;
      io.skip_amount(M - 2);

      darr(i, 0) = -2;
      for(int j = 1; j + 1 < M; j++) {
        darr(i, j) = -1;
        if(base[j] == 'S') {
          ss = arr(i, j);
        } else if(base[j] == 'F') {
          tt = arr(i, j);
        } else if(base[j] != '.') {
          darr(i, j) = -2;
        }
      }
      darr(i, M - 1) = -2;
    }

    int* qf = Q;
    int* qe = Q;
    *qe++ = ss;
    *qe++ = tt;
    darrv(ss) = 0;
    darrv(tt) = 1 << 30;
    for(; qf != qe;) {
      int u = *qf++;
      int dd = darrv(u) + 1;

#define DOSTUFF() { \
          if(__builtin_expect(*vd == -1, 0)) { \
            *vd = dd; \
            *qe++ = vd - D; \
          } else if(__builtin_expect(*vd != dd, 1)) { \
            if(__builtin_expect((*vd ^ dd) >> 30 == 1, 0)) { \
              printf("%d\n", (*vd + dd) ^ (1 << 30)); \
              goto nextcase; \
            } \
            break; \
          } \
        }

#define DOIT(dr, dc) do { \
          for(int* vd = &darrv(u);;) { \
            vd += arr(dr, dc); DOSTUFF(); \
          } \
        } while(0)

      DOIT(-1, -1);
      DOIT(-1, 0);
      DOIT(-1, 1);
      DOIT(0, -1);
      DOIT(0, 1);
      DOIT(1, -1);
      DOIT(1, 0);
      DOIT(1, 1);
    }
    puts("hahahahaha, there are no unreachable cases!");

nextcase:
    t = t;
  }
  return 0;
}