ปริศนา 15: บทเรียนเรื่องการอ่านโจทย์ให้เจอว่ามันขอน้อยกว่าที่คิด

#include <bits/stdc++.h>
using namespace std;

int g[16];              // g[i] = หมายเลขหมากในช่อง i (0 = ช่องว่าง)
bool lockd[16];         // ช่องที่เข้าที่แล้ว ห้ามแตะอีก
int bl;                 // ช่องว่างอยู่ที่ไหน
string ans;

const int DR[4] = {-1, 0, 1, 0};
const int DC[4] = {0, 1, 0, -1};
const char LET[4] = {'N', 'E', 'S', 'W'};   // ทิศที่ "ช่องว่าง" ขยับไป

// ช่องปลายทางเมื่อช่องว่างที่ p ขยับไปทาง d (คืน -1 ถ้าตกขอบหรือชนช่องที่ล็อกไว้)
int nb(int p, int d) {
    int r = p / 4 + DR[d], c = p % 4 + DC[d];
    if (r < 0 || r > 3 || c < 0 || c > 3) return -1;
    int q = r * 4 + c;
    return lockd[q] ? -1 : q;
}

void apply1(int d) {
    int q = nb(bl, d);
    g[bl] = g[q];
    g[q] = 0;
    bl = q;
    ans += LET[d];
}

// วางหมากตัวเดียว: สถานะคือ (ช่องของหมาก, ช่องว่าง) มีไม่เกิน 16 x 16 แบบ
void placeOne(int v, int goal) {
    int start = (int)(find(g, g + 16, v) - g) * 16 + bl;
    vector<int> from(256, -2);
    vector<char> dir(256, -1);
    from[start] = -1;
    queue<int> q;
    q.push(start);
    int end = -1;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        int tp = s >> 4, bp = s & 15;
        if (tp == goal) { end = s; break; }
        for (int d = 0; d < 4; d++) {
            int np = nb(bp, d);
            if (np < 0) continue;
            int ntp = (np == tp) ? bp : tp;      // ช่องว่างเดินทับหมาก = หมากถูกดันมาที่เดิมของช่องว่าง
            int ns = ntp * 16 + np;
            if (from[ns] != -2) continue;
            from[ns] = s; dir[ns] = (char)d;
            q.push(ns);
        }
    }
    vector<int> path;
    for (int s = end; from[s] != -1; s = from[s]) path.push_back(dir[s]);
    reverse(path.begin(), path.end());
    for (int d : path) apply1(d);
    lockd[goal] = true;
}

// วางหมากสองตัวท้ายแถวพร้อมกัน: สถานะคือ (ช่อง A, ช่อง B, ช่องว่าง) มีไม่เกิน 16^3 แบบ
void placePair(int va, int vb, int ga, int gb) {
    int pa = (int)(find(g, g + 16, va) - g), pb = (int)(find(g, g + 16, vb) - g);
    int start = (pa * 16 + pb) * 16 + bl;
    vector<int> from(4096, -2);
    vector<char> dir(4096, -1);
    from[start] = -1;
    queue<int> q;
    q.push(start);
    int end = -1;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        int ap = s >> 8, bp = (s >> 4) & 15, bk = s & 15;
        if (ap == ga && bp == gb) { end = s; break; }
        for (int d = 0; d < 4; d++) {
            int np = nb(bk, d);
            if (np < 0) continue;
            int nap = (np == ap) ? bk : ap;
            int nbp = (np == bp) ? bk : bp;
            int ns = (nap * 16 + nbp) * 16 + np;
            if (from[ns] != -2) continue;
            from[ns] = s; dir[ns] = (char)d;
            q.push(ns);
        }
    }
    vector<int> path;
    for (int s = end; from[s] != -1; s = from[s]) path.push_back(dir[s]);
    reverse(path.begin(), path.end());
    for (int d : path) apply1(d);
    lockd[ga] = lockd[gb] = true;
}

// สองแถวล่างที่เหลือ: แปดช่อง เรียงได้ 8! = 40320 แบบ ค้นทีเดียวจบ
int fct[9];

int rankPerm(const int a[8]) {
    int r = 0;
    for (int i = 0; i < 8; i++) {
        int less = 0;
        for (int j = i + 1; j < 8; j++) if (a[j] < a[i]) less++;
        r += less * fct[7 - i];
    }
    return r;
}

void unrankPerm(int r, int a[8]) {
    int pool[8] = {0, 1, 2, 3, 4, 5, 6, 7}, n = 8;
    for (int i = 0; i < 8; i++) {
        int k = r / fct[7 - i];
        r %= fct[7 - i];
        a[i] = pool[k];
        for (int j = k; j < n - 1; j++) pool[j] = pool[j + 1];
        n--;
    }
}

void finishBottom() {
    fct[0] = 1;
    for (int i = 1; i <= 8; i++) fct[i] = fct[i - 1] * i;

    int cur[8], goal[8];
    for (int i = 0; i < 8; i++) {
        cur[i] = g[8 + i] == 0 ? 7 : g[8 + i] - 9;   // ช่องว่างเป็นเลข 7 หมาก 9..15 เป็น 0..6
        goal[i] = i;
    }
    int start = rankPerm(cur), target = rankPerm(goal);

    vector<int> from(40320, -2);
    vector<char> dir(40320, -1);
    from[start] = -1;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int s = q.front(); q.pop();
        if (s == target) break;
        int a[8];
        unrankPerm(s, a);
        int z = 0;
        while (a[z] != 7) z++;
        for (int d = 0; d < 4; d++) {
            int nr = z / 4 + DR[d], nc = z % 4 + DC[d];
            if (nr < 0 || nr > 1 || nc < 0 || nc > 3) continue;   // ขยับได้เฉพาะในกระดานย่อยสองแถว
            int nz = nr * 4 + nc;
            int b[8];
            memcpy(b, a, sizeof b);
            swap(b[z], b[nz]);
            int ns = rankPerm(b);
            if (from[ns] != -2) continue;
            from[ns] = s; dir[ns] = (char)d;
            q.push(ns);
        }
    }
    vector<int> path;
    for (int s = target; from[s] != -1; s = from[s]) path.push_back(dir[s]);
    reverse(path.begin(), path.end());
    for (int d : path) apply1(d);
}

int main() {
    for (int i = 0; i < 16; i++) {
        if (!(cin >> g[i])) return 0;
        if (g[i] == 0) bl = i;
    }

    for (int r = 0; r < 2; r++) {
        placeOne(4 * r + 1, r * 4 + 0);
        placeOne(4 * r + 2, r * 4 + 1);
        placePair(4 * r + 3, 4 * r + 4, r * 4 + 2, r * 4 + 3);
    }
    finishBottom();

    cout << ans << '\n';
    return 0;
}