Updated solution to SPOJ's QUEEN

queen2.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 <cstdlib>

#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 N;
int M;
char* Q[1 << 20];
char V[1 << 20];

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 NW = (N * M + 3) / 4;

    memset(V, 64, M);
    for(int i = 1; i + 1 < N; i++) {
      io.skip_space();
      V[i * M + 0] = 64;
      memcpy(V + i * M + 1, io.sin, M - 2);
      V[i * M + M - 1] = 64;
      io.skip_amount(M - 2);
    }
    memset(V + (N - 1) * M, 64, M);

    int ss = -1, tt = -1;
    for(int* vout = (int*)V; ; vout += 8) {
      if(__builtin_expect(((vout[0] - 0x14141414) |
                           (vout[1] - 0x14141414) |
                           (vout[2] - 0x14141414) |
                           (vout[3] - 0x14141414) |
                           (vout[4] - 0x14141414) |
                           (vout[5] - 0x14141414) |
                           (vout[6] - 0x14141414) |
                           (vout[7] - 0x14141414)) & 0x20202020, 0)) {
        int ib = (char*)vout - V;
        for(int k = ib; k < ib + 4 * 8; k++) {
          if(ss == -1 && V[k] == 'S') {
            ss = k;
          } else if(tt == -1 && V[k] == 'F') {
            tt = k;
          }
        }
        if(ss != -1 && tt != -1) {
          break;
        }
      }
    }

    {
      int* vout = (int*)V;
      int* voute = (int*)V + (NW + 7) / 8 * 8;
      for(; vout != voute; ) {
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
        *vout++ &= 0x40404040;
      }
    }

/*
printf("%d %d %d %d\n", ss / M, ss % M, tt / M, tt % M);
for(int i = 0; i < N; i++) {
  for(int j = 0; j < M; j++) printf("%2d ", (int)V[i * M + j]);
printf("\n");
}
*/
    int result = -1;
    char** qf = Q;
    char** qe = Q;
    *qe++ = V + ss;
    char** qdiv1 = qe;
    *qe++ = V + tt;
    char** qdiv2 = qe;

    V[ss] = 128 | 16;
    V[tt] = 128 | 32;

#define DOSTUFF(side, oside, m) { \
          if(*vd & (m | 64)) { \
            break; \
          } else if (*vd == 0) { \
            *qe++ = vd; \
          } \
          *vd |= m | side | 128; \
        }

#define DOIT(side, oside, m, dr, dc) do { \
          for(char* vd = ud;;) { \
            vd += (dr * M + dc); DOSTUFF(side, oside, m); \
          } \
        } while(0)

#define DOALL(s, os) do { \
          static void* dispatch_ ## s[] = { \
            &&case0_ ## s, \
            &&case1_ ## s, \
            &&case2_ ## s, \
            &&case3_ ## s, \
            &&case4_ ## s, \
            &&case5_ ## s, \
            &&case6_ ## s, \
            &&case7_ ## s, \
            &&case8_ ## s, \
            &&case9_ ## s, \
            &&case10_ ## s, \
            &&case11_ ## s, \
            &&case12_ ## s, \
            &&case13_ ## s, \
            &&case14_ ## s, \
            &&case15_ ## s, \
          }; \
        goto *dispatch_ ## s[*ud & 15]; \
          case0_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case1_ ## s: \
            DOIT(s, os, 2, -1, 0); DOIT(s, os, 2, 1, 0); \
            DOIT(s, os, 4, 0, -1); DOIT(s, os, 4, 0, 1); \
            DOIT(s, os, 8, -1, 1); DOIT(s, os, 8, 1, -1); \
        break; \
          case2_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case3_ ## s: \
            DOIT(s, os, 4, 0, -1); DOIT(s, os, 4, 0, 1); \
            DOIT(s, os, 8, -1, 1); DOIT(s, os, 8, 1, -1); \
        break; \
          case4_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case5_ ## s: \
            DOIT(s, os, 2, -1, 0); DOIT(s, os, 2, 1, 0); \
            DOIT(s, os, 8, -1, 1); DOIT(s, os, 8, 1, -1); \
        break; \
          case6_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case7_ ## s: \
            DOIT(s, os, 8, -1, 1); DOIT(s, os, 8, 1, -1); \
        break; \
          case8_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case9_ ## s: \
            DOIT(s, os, 4, 0, -1); DOIT(s, os, 4, 0, 1); \
            DOIT(s, os, 2, -1, 0); DOIT(s, os, 2, 1, 0); \
        break; \
          case10_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case11_ ## s: \
            DOIT(s, os, 4, 0, -1); DOIT(s, os, 4, 0, 1); \
        break; \
          case12_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case13_ ## s: \
            DOIT(s, os, 2, -1, 0); DOIT(s, os, 2, 1, 0); \
        break; \
          case14_ ## s: \
            DOIT(s, os, 1, -1, -1); DOIT(s, os, 1, 1, 1); \
          case15_ ## s: \
        break; \
        } while(0)

    for(++result; qf != qe; ) {
      for(; qf != qdiv1; ) {
        char* ud = *qf++;
        if(*ud & 32) {
          goto nextcase;
        }
        DOALL(16, 32);
      }
      qdiv1 = qe;
      ++result;

      for(; qf != qdiv2; ) {
        char* ud = *qf++;
        if(*ud & 16) {
          goto nextcase;
        }
        DOALL(32, 16);
      }
      qdiv2 = qe;
      ++result;
    }


nextcase:
    printf("%d\n", result);
  }
  return 0;
}