学步园

/**
*    DFS: 深搜题
*    这题需要输出移动步骤，所以用深搜可以记录步骤。
*    关键是地图的建立。 依题墙是1 * n 的，换句话说墙是不占格子的，
*  在地图上只是一条线。 所以在建立地图的时候用二维数组map[i][j] 然而对应的格子坐标应该是 i / 2, j / 2
*  也就是把输入给的格子坐标都扩大两倍，而且在移动的是也是+2 -2 的移动，这样在两个格子之间就可以存下墙的位置了
*  而且，可以区分出，当两坐标都为偶数的时候是专门用来放格子的，当坐标是一奇一偶的时候是专门用来存墙的位置的
*  这样就可以很方便的dfs了。  另外map[i][j] 是用来记录要到达 i / 2 , j / 2 这个格子所需的最小步骤，用来判重的.
*  0ms  1A
*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define INF 0x7fffffff
#define DEBUG 0
#define MAXS 14
#define LL long long
using namespace std;
int map[MAXS][MAXS], curStack[50], ansStack[50];
int ans, sx, sy, ex, ey;
int dir[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};
char chDir[5] = {"EWSN"};
int wall[4][4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void update(int xx1, int yy1, int xx2, int yy2, int isHo) {
    int len;
    len = isHo ? xx2 - xx1 : yy2 - yy1;
    xx1 *= 2; yy1 *= 2;
    if(isHo) {
        for(int i = 1; i <= len; i ++) {
             map[yy1 + 1][xx1 + i * 2] = -1;
        }
    } else {
        for(int i = 1; i <= len; i ++) {
            map[yy1 + i * 2][xx1 + 1] = -1;
        }
    }
}

void dfs(int x, int y, int cur) {
    if(x == ex && y == ey && cur < ans) {
        if(cur < ans) {
            ans = cur;
            for(int i = 0; i <= cur; i ++ )
                ansStack[i] = curStack[i];
        }
        return ;
    }
    map[y][x] = cur;
    for(int i = 0; i < 4; i ++) {
        if(cur + 1 < map[y + dir[i][1]][x + dir[i][0]] &&
           map[y + wall[i][1]][x + wall[i][0]] != -1) {
            curStack[cur + 1] = chDir[i];
            dfs(x + dir[i][0], y + dir[i][1], cur + 1);
        }
    }

    return ;
}

void init() {
    sx *= 2, sy *= 2, ex *= 2, ey *= 2;
    ans = INF;
    for(int i = 0; i <= 13; i ++) {
        for(int j = 0; j <= 13; j ++)
            map[i][j] = INF;
    }
    for(int i = 1; i <= 13; i ++)
        map[i][1] = map[1][i] = map[13][i] = map[i][13] = -1;
}

int main()
{
    while(scanf("%d%d", &sx, &sy)) {
        if(sx == sy && sx == 0) break;
        scanf("%d%d", &ex, &ey);
        init();
        for(int i = 0; i < 3; i ++) {
            int xx1, yy1, xx2, yy2;
            scanf("%d%d%d%d", &xx1, &yy1, &xx2, &yy2);
            if(xx2 > xx1) update(xx1, yy1, xx2, yy2, 1);
            else          update(xx1, yy1, xx2, yy2, 0);
        }

        dfs(sx, sy, 0);
        for(int i = 1; i <= ans; i ++)
            printf("%c", ansStack[i]);
        printf("\n");

    }
    return 0;
}