SAMPLE INPUT (file robots.in):

5 4
####
#X.#
#..#
...#
##.#
1
4 3 2 W
4 4
####
#...
#X.#
####
0

OUTPUT FORMAT:

* Line 1: A single integer K (K <= 10000), the number of commands for
        both robots to exit the maze without being captured. If no
        such sequence exists, output a single line containing ``-1''.

SAMPLE OUTPUT (file robots.out):

8

OUTPUT DETAILS:

E N E S S S E S will do the trick; nothing shorter will.

/*
ID: iceeight1
LANG: C++
TASK: robots
SOURCE: IOI 2003
*/

#include <stdio.h>
#include <iostream>
#include <queue>
#define MAXD 25
#define MAXG 12
#define MAXP 12
#define OUT 22
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

const int dy[4] = { -1, 0, 1, 0 },
          dx[4] = { 0, 1, 0, -1 };

struct loc {
    int y, x;
    loc() {}
    loc(int _y, int _x): y(_y), x(_x) {}
    bool operator==(loc a) { return y == a.y && x == a.x; }
};

struct state {
    loc a, b; int d;
    state(loc _a, loc _b, int _d) { a = _a; b = _b; d = _d; }
};

int R[2], C[2], map[2][MAXD][MAXD]; loc s[2];
int G[2]; loc g[2][MAXG][MAXP];
queue<state> q; bool seen[MAXD][MAXD][MAXD][MAXD][MAXP];

bool mark(loc a, loc b, int p) {
    if (seen[a.y][a.x][b.y][b.x][p]) return false;
    return seen[a.y][a.x][b.y][b.x][p] = true;
}

int main() {
    FILE *fin = fopen("robots.in", "r"),
         *fout = fopen("robots.out", "w");
    REP(n, 2) {
        fscanf(fin, "%d %d\n", &R[n], &C[n]);
        REP(i, R[n]) {
            REP(j, C[n]) {
                char c; fscanf(fin, "%c", &c);
                if (c == '#') map[n][i][j] = 1;
                if (c == 'X') s[n] = loc(i, j);
            }
            fscanf(fin, "\n");
        }
        fscanf(fin, "%d", &G[n]);
        REP(i, G[n]) {
            int y, x, p; char c; fscanf(fin, "%d %d %d %c", &y,
&x, &p, &c); y--; x--;
            int dy = 0, dx = 0; if (c == 'N') dy = -1; if (c ==
'S') dy = 1; if (c == 'E') dx = 1; if (c == 'W') dx = -1;
            g[n][i][0] = loc(y, x);
            FOR(j, 1, MAXP-1) {
                g[n][i][j] = loc(g[n][i][j-1].y+dy, g[n][i][j-
1].x+dx);
                if (j%(p-1) == 0) dy *= -1, dx *= -1;
            }
        }
    }

    q.push(state(s[0], s[1], 0)); mark(s[0], s[1], 0);
    while(!q.empty()) {
        state top = q.front(); q.pop();
        loc c[2]; c[0] = top.a, c[1] = top.b; int d = top.d;
        if (c[0].y == OUT && c[1].y == OUT) {
            fprintf(fout, "%d\n", d);
            return 0;
        }

        REP(i, 4) {
            loc n[2]; REP(j, 2) {
                if (map[j][c[j].y+dy[i]][c[j].x+dx[i]] == 1)
n[j] = c[j];
                else n[j].y = c[j].y+dy[i], n[j].x =
c[j].x+dx[i];
                if (c[j].y == OUT || n[j].y < 0 || n[j].y
>= R[j] || n[j].x < 0 || n[j].x >= C[j]) n[j] = loc(OUT, OUT);
            }
            int nd = d+1;
            bool bad = false; REP(j, 2) if (n[j].y != OUT) REP(k,
G[j]) {
                if (n[j] == g[j][k][nd%MAXP]) bad = true;
                if (n[j] == g[j][k][d%MAXP] && c[j] ==
g[j][k][nd%MAXP]) bad = true;
            }
            if (!bad && mark(n[0], n[1], nd%MAXP))
q.push(state(n[0], n[1], nd));
        }
    }
    fprintf(fout, "-1\n");
    return 0;
}

You are the proud owner of two robots that are located in separate
rectangular mazes each of which has no more than 20 rows or columns.
Square (1, 1) in a maze is the square in the upper-left (northwest)
corner.  Maze i (i = 1, 2) has a set of G_i (0 <= G_i <= 10) guards
trying to capture the robots. They patrol back and forth on a
straight patrol path.

Your goal is to determine a sequence of robot commands such that
both robots exit the mazes without either robot being captured by
a guard.

Each robot command is a direction (north, south, east, or west).
At the beginning of each minute, you broadcast the same command to
both robots. A robot moves one square in the direction of the
command, unless the robot would collide with a wall, in which case
the robot does not move for that minute. A robot exits the maze by
walking out of it. A robot ignores commands after it has exited its
maze.

Guards move one square at the beginning of each minute, at the same
time as the robots. Each guard begins at a given square facing a
given direction and moves forward one square per minute until the
guard has moved one fewer square than the number of squares in his
patrol path. The guard then turns around instantaneously and walks
in the opposite direction back to his starting square, where he
again turns around and repeats his patrol path until each robot has
exited its maze. A guard's patrol will not require the guard to
walk through walls or exit the maze.

Although guard patrols may overlap, no two guards will ever collide:
they will never occupy the same square at the end of a minute, and
they will not exchange squares with each other during a minute. A
guard in a maze will not start in the same square as the robot in
that maze.  A guard captures a robot if the guard occupies the same
square at the end of a minute as the robot, or if the guard and the
robot exchange squares with each other during a minute.

Given the layout of the two mazes along with the initial square of
each robot and the patrol paths of the guards in each maze, determine
a sequence of commands for which the robots exit without being
caught by the guards. Minimize the time it takes for the later robot
to exit its maze. If the robots exit at different times, the time
at which the earlier robot exited does not matter.

TIME LIMIT: 5 seconds
（其实我的程序全部在USACO的老爷机上2s内解决）