A1646 骑士精神

// A1646 骑士精神 —— 状态压缩 BFS
//
// 棋盘 5×5：12 个白骑士(0)、12 个黑骑士(1)、1 个空位(*)。
// 每一步把一个与空位构成「马步」的骑士跳到空位上（两个格子交换）。
// 求 15 步以内到达目标棋盘的最少步数，走不到输出 -1。
//
// 目标棋盘（题面图片）：
//   11111
//   01111
//   00*11
//   00001
//   00000
//
// 状态编码：白骑士位置的 25 位掩码 << 5 | 空位下标，共 30 位。
// BFS 按层扩展，第 d 层就是恰好 d 步能到的状态，第一次碰到目标即最少步数。
// 判重用开放寻址哈希表（比 unordered_set 快很多，状态数可达百万级）。

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

const int W = 5;
const string TARGET = string("11111") + "01111" + "00*11" + "00001" + "00000";

const int dr[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dc[8] = {2, -2, 2, -2, 1, -1, 1, -1};

// 开放寻址哈希集合：存 key+1，0 表示空槽
struct StateSet {
    vector<uint32_t> slot;
    size_t mask = 0, cnt = 0;

    StateSet() { init(1u << 16); }

    void init(size_t cap) {
        slot.assign(cap, 0);
        mask = cap - 1;
        cnt = 0;
    }

    static uint32_t hash(uint32_t k) {
        k ^= k >> 16;
        k *= 0x7feb352dU;
        k ^= k >> 15;
        k *= 0x846ca68bU;
        k ^= k >> 16;
        return k;
    }

    void grow() {
        vector<uint32_t> old;
        old.swap(slot);
        init(old.size() * 2);
        for (uint32_t v : old) {
            if (!v) continue;
            uint32_t key = v - 1;
            size_t i = hash(key) & mask;
            while (slot[i]) i = (i + 1) & mask;
            slot[i] = v;
            cnt++;
        }
    }

    // 返回 true 表示是新插入的
    bool insert(uint32_t key) {
        if ((cnt + 1) * 2 >= slot.size()) grow();
        uint32_t v = key + 1;
        size_t i = hash(key) & mask;
        while (slot[i]) {
            if (slot[i] == v) return false;
            i = (i + 1) & mask;
        }
        slot[i] = v;
        cnt++;
        return true;
    }
};

uint32_t encode(const vector<string> &board) {
    uint32_t white = 0;
    int empty = 0;
    for (int r = 0; r < W; r++) {
        for (int c = 0; c < W; c++) {
            if (board[r][c] == '0') white |= (1u << (r * W + c));
            if (board[r][c] == '*') empty = r * W + c;
        }
    }
    return (white << 5) | (uint32_t)empty;
}

int bfs(uint32_t start, uint32_t goal) {
    if (start == goal) return 0;

    StateSet vis;
    vis.insert(start);
    vector<uint32_t> cur{start};

    for (int d = 1; d <= 15; d++) {
        vector<uint32_t> nxt;
        for (uint32_t key : cur) {
            uint32_t white = key >> 5;
            int empty = (int)(key & 31u);
            int er = empty / W, ec = empty % W;
            for (int k = 0; k < 8; k++) {
                int nr = er + dr[k], nc = ec + dc[k];
                if (nr < 0 || nr >= W || nc < 0 || nc >= W) continue;
                int p = nr * W + nc;
                uint32_t nwhite = white;
                if ((white >> p) & 1u) { // 白骑士跳进空位：原格变空位，空位变白
                    nwhite &= ~(1u << p);
                    nwhite |= (1u << empty);
                }
                uint32_t nk = (nwhite << 5) | (uint32_t)p; // 空位移到骑士原来的格子
                if (!vis.insert(nk)) continue;
                if (nk == goal) return d;
                nxt.push_back(nk);
            }
        }
        cur.swap(nxt);
        if (cur.empty()) break;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> t(5);
    for (int i = 0; i < 5; i++) t[i] = TARGET.substr(i * 5, 5);
    uint32_t goal = encode(t);

    int T;
    cin >> T;
    while (T--) {
        vector<string> board(W);
        for (int i = 0; i < W; i++) cin >> board[i];
        cout << bfs(encode(board), goal) << '\n';
    }
    return 0;
}