2018-10-19

题

如下的 3x3 矩阵里，x 可以与相邻的数字交换位置。

1 2 3
x 4 6
7 5 8

游戏目的是达到下面的局面：

1 2 3
4 5 6
7 8 x

输入一个游戏局面，输出可以达成目的的操作序列（每一步 x 与哪个方向的数交换）。如果不能达到目的，输出 unsolvable。

任何一种可行的解都可以达到目的。

解

从目标局面反向搜索。共计有 181440 个可以解的答案，将答案都保存起来待之后查询。朴素地将所有的状态用 std::string 保存得到了 MLE。但我不愿写康托展开，改而将位置数字压缩到长整数中，x 以 0 表示。

到此可通过这个题。但我的资源消耗还是比较多的，可能数据量比较少每组直接搜索可以通过吧。可以考虑康托展开压缩空间；发现最大答案只有 31 个步骤，所以答案可以压缩到 2x31 = 62 位的整数里，再压缩空间；还可以将询问都保存起来，搜索的时候搜到所有的答案即停止，可以压缩时间和空间。

码

#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <functional>
#include <algorithm>
#include <cstdint>
#include <cassert>

typedef unsigned long long ull;
typedef unsigned uint;

bool GetNextCase(std::string& s) {
    s.clear();

    static char tmp[3];

    for (int i = 0; i < 9; ++i) {
        std::cin >> tmp;

        if (!std::cin) {
            return false;
        }

        s += tmp[0];
    }

    return true;
}

ull StagePack(std::string s) {
    std::reverse(s.begin(), s.end());

    ull p = 0;

    for (int i = 0; i < 9; ++i) {
        p <<= 4;

        if (s[i] == 'x') {
            p |= 0;
        } else {
            p |= s[i] - '0';
        }
    }
    return p;
}

uint GetStagePack(ull p, int i) {
    return (uint) ((p >> (4 * i)) & 0xf);
}

ull SetStagePack(ull p, int i, ull v) {
    i *= 4;
    p = ((p & (~(ull{0xf} << i))) | (v << i));
    return p;
}

std::string UnpackStage(ull p) {
    std::string s;

    for (int i = 0; i < 9; ++i) {
        int si = (int)(p & 0xf);

        assert(si >= 0 && si < 9);
        if (si == 0) {
            s += 'x';
        } else {
            s += (char)('0' + si);
        }
        
        p >>= 4;
    }

    return s;
}

ull StagePackSwap(ull p, int i, int j) {
    uint pi = GetStagePack(p, i);
    uint pj = GetStagePack(p, j);

    p = SetStagePack(p, i, pj);
    p = SetStagePack(p, j, pi);
    return p;
}

struct Stage {
    ull stage;
    int xpos;
};

typedef std::map<ull, std::string> SolutionMap;

SolutionMap GetSolutions() {
    Stage initial;

    initial.stage = StagePack("12345678x");
    initial.xpos = 8;

    std::queue<Stage> blob;

    blob.emplace(initial);

    SolutionMap sln;

    sln[initial.stage] = "";

    std::array<int, 9> step[4];
    {
        auto& lstep = step[0];

        for (int i = 0; i < 9; ++i) {
            lstep[i] = i - 1;
            if (i % 3 == 0) {
                lstep[i] = -1;
            }
        }

        auto& rstep = step[1];

        for (int i = 0; i < 9; ++i) {
            rstep[i] = i + 1;
            if (i % 3 == 2) {
                rstep[i] = -1;
            }
        }

        auto& ustep = step[2];

        for (int i = 0; i < 9; ++i) {
            ustep[i] = i - 3;
        }

        auto& dstep = step[3];

        for (int i = 0; i < 9; ++i) {
            dstep[i] = i + 3;
        }
    }

    char step_name[4] = {'r', 'l', 'd', 'u'};

    while (!blob.empty()) {
        Stage curr = blob.front();
        blob.pop();

        int xpos = curr.xpos;

        for (int i = 0; i < 4; ++i) {
            int nxpos = step[i][xpos];

            if (nxpos < 0 || nxpos >= 9) {
                continue;
            }

            ull stage = curr.stage;

            stage = StagePackSwap(stage, xpos, nxpos);

            auto iter_next = sln.find(stage);

            if (iter_next != sln.end()) {
                continue;
            }

            sln.emplace(stage, sln[curr.stage] + step_name[i]);

            Stage next{stage, nxpos};

            blob.emplace(std::move(next));
        }

        if (sln.size() > 200000) {
            std::cerr << "large solution size\n";
            break;
        }
    }

    return sln;
}

int main() {
    auto sln = GetSolutions();

    std::string s;

    while (GetNextCase(s)) {
        auto iter = sln.find(StagePack(s));

        if (iter == sln.end()) {
            std::cout << "unsolvable\n";
        } else {
            std::string res = iter->second;

            std::reverse(res.begin(), res.end());
            std::cout << res << std::endl;
        }
    }
    return 0;
}