启发式搜索、双向 BFS 与迭代加深

struct Node {
    int f, g;   // f = g + h，h 由估价函数现算
    State s;     // 状态本身
    bool operator<(const Node& o) const {
        return f > o.f;   // 优先队列默认大根堆，所以反向定义
    }
};

int astar(State st) {
    priority_queue<Node> pq;
    best[st] = 0;
    pq.push({h(st), 0, st});
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (isGoal(u.s)) return u.g;      // 首次弹出即最优
        if (u.g > best[u.s]) continue;        // 过期状态，跳过
        for (每个后继 v) {
            int ng = u.g + w(u.s, v);
            if (ng < best[v] 或 v 未访问) {
                best[v] = ng;
                pq.push({ng + h(v), ng, v});
            }
        }
    }
    return -1;   // 无解
}

int bidBFS(State S, State T) {
    if (S == T) return 0;
    queue<State> q1, q2;
    unordered_map<State, int> d1, d2;
    q1.push(S); d1[S] = 0;
    q2.push(T); d2[T] = 0;
    while (!q1.empty() && !q2.empty()) {
        // 关键优化：只扩展较小的一侧
        if (q1.size() > q2.size()) { swap(q1, q2); swap(d1, d2); }
        int sz = q1.size();
        while (sz--) {                        // 只扩"一整层"，保证层数同步
            State u = q1.front(); q1.pop();
            for (State v : nxt(u)) {
                int step = d1[u] + 1;
                if (d2.count(v)) return step + d2[v];  // 相遇！
                if (d1.count(v)) continue;           // 自己这边已访问
                d1[v] = step; q1.push(v);
            }
        }
    }
    return -1;
}

int limit;

bool dfs(State u, int dep) {
    if (dep > limit) return false;        // 超出深度上限，剪掉
    if (isGoal(u)) return true;
    for (State v : nxt(u)) {
        if (dep + 1 > limit) continue;   // 也可用估价 h 进一步提前剪枝
        if (dfs(v, dep + 1)) return true;
    }
    return false;
}

int iddfs(State st, int maxDep) {
    for (limit = 0; limit <= maxDep; limit++)
        if (dfs(st, 0)) return limit;
    return -1;
}

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

string S;                              // 初始局面
const string T = "123456780";        // 目标局面
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int bfs() {
    if (S == T) return 0;

    queue<string> q1, q2;                // q1 从起点扩展，q2 从目标扩展
    unordered_map<string, int> d1, d2;  // 两侧各自的距离表
    q1.push(S); d1[S] = 0;
    q2.push(T); d2[T] = 0;

    while (!q1.empty() && !q2.empty()) {
        // 关键优化：总是扩展队列较小的一侧
        if (q1.size() > q2.size()) { swap(q1, q2); swap(d1, d2); }

        int sz = q1.size();              // 只扩展"一整层"，保证两侧层数可比
        while (sz--) {
            string cur = q1.front(); q1.pop();

            int id = cur.find('0');        // 空格的一维下标
            int x = id / 3, y = id % 3;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;

                string nxt = cur;
                swap(nxt[id], nxt[nx * 3 + ny]);   // 交换空格与滑块

                int step = d1[cur] + 1;              // 走一步的代价
                if (d2.count(nxt)) return step + d2[nxt];  // ① 两侧相遇
                if (d1.count(nxt)) continue;             // ② 自己这边已访问过

                d1[nxt] = step;
                q1.push(nxt);
            }
        }
    }
    return -1;                          // 不可达（逆序数为奇数）
}

int main() {
    ios::sync_with_stdio(0);
    cin >> S;
    cout << bfs() << "\n";
    return 0;
}

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

int n, sx, sy, tx, ty, limit;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

// 可采纳估价：马一步单轴最多走 2 格
int h(int x, int y) {
    int a = abs(x - tx), b = abs(y - ty);
    return max((a + 1) / 2, (b + 1) / 2);
}

bool dfs(int x, int y, int dep, int px, int py) {
    if (dep + h(x, y) > limit) return false;   // 预算不够，剪枝
    if (x == tx && y == ty) return true;          // 命中目标

    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (nx == px && ny == py) continue;          // 不走回头路
        if (dfs(nx, ny, dep + 1, x, y)) return true;
    }
    return false;
}

int main() {
    cin >> n >> sx >> sy >> tx >> ty;
    // 逐层放宽深度上限
    for (limit = 0; limit <= 2 * n; limit++) {
        if (dfs(sx, sy, 0, -1, -1)) {
            cout << limit << "\n";
            break;
        }
    }
    return 0;
}

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

const int KX[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int KY[8] = {1, 2, 2, 1, -1, -2, -2, -1};

// 目标局面：与输入局面逐格比较，得出"错位数"
const char G[5][6] = {
    "11111",
    "01111",
    "00*11",
    "00001",
    "00000"
};

int LIMIT, ans;
string board;

int h() {                        // 乐观估价：错位格子数
    int c = 0;
    for (int i = 0; i < 25; i++)
        if (board[i] != '*' && board[i] != G[i / 5][i % 5]) c++;
    return c;
}

bool ida(int blank, int dep, int pre, int& nxtLimit) {
    int g = h();
    if (dep + g > LIMIT) { nxtLimit = min(nxtLimit, dep + g); return false; }
    if (g == 0) return true;            // 已与目标一致

    int x = blank / 5, y = blank % 5;
    for (int k = 0; k < 8; k++) {
        int nx = x + KX[k], ny = y + KY[k];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        int np = nx * 5 + ny;
        if (np == pre) continue;             // 不走回头路

        swap(board[blank], board[np]);
        bool ok = ida(np, dep + 1, blank, nxtLimit);
        swap(board[blank], board[np]);          // 回溯
        if (ok) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) {
        board.clear();
        for (int i = 0; i < 5; i++) { string row; cin >> row; board += row; }
        int blank = board.find('*');
        ans = -1;
        for (LIMIT = h(); LIMIT <= 15; ) {     // f 值上限递增
            int nxtLimit = INT_MAX;
            if (ida(blank, 0, -1, nxtLimit)) { ans = LIMIT; break; }
            if (nxtLimit == INT_MAX) break;      // 搜索树完整展开仍无解
            LIMIT = nxtLimit;                     // 直接跳到"最小超限 f 值"，比加 1 快
        }
        cout << ans << "\n";
    }
    return 0;
}

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

string S;
const string T = "123456780";
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int bfs() {
    if (S == T) return 0;
    queue<string> q1, q2;
    unordered_map<string, int> d1, d2;
    q1.push(S); d1[S] = 0;
    q2.push(T); d2[T] = 0;

    while (!q1.empty() && !q2.empty()) {
        if (q1.size() > q2.size()) { swap(q1, q2); swap(d1, d2); }
        int sz = q1.size();
        while (sz--) {
            string cur = q1.front(); q1.pop();
            int id = cur.find('0');
            int x = id / 3, y = id % 3;
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
                string nxt = cur;
                swap(nxt[id], nxt[nx * 3 + ny]);
                int step = d1[cur] + 1;
                if (d2.count(nxt)) return step + d2[nxt];
                if (d1.count(nxt)) continue;
                d1[nxt] = step;
                q1.push(nxt);
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> S;
    cout << bfs() << "\n";
    return 0;
}

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

int n, sx, sy, tx, ty, limit;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

int h(int x, int y) {
    int a = abs(x - tx), b = abs(y - ty);
    return max((a + 1) / 2, (b + 1) / 2);
}

bool dfs(int x, int y, int dep, int px, int py) {
    if (dep + h(x, y) > limit) return false;
    if (x == tx && y == ty) return true;
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (nx == px && ny == py) continue;
        if (dfs(nx, ny, dep + 1, x, y)) return true;
    }
    return false;
}

int main() {
    cin >> n >> sx >> sy >> tx >> ty;
    for (limit = 0; limit <= 2 * n; limit++)
        if (dfs(sx, sy, 0, -1, -1)) { cout << limit << "\n"; break; }
    return 0;
}

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

const int GOAL = 123456780;
int gx[10], gy[10];          // 数字 d 的目标行列
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int hval(int s) {                 // 曼哈顿距离之和
    int sum = 0;
    for (int i = 8; i >= 0; i--) {
        int d = s % 10; s /= 10;
        if (d == 0) continue;             // 空格不计入
        sum += abs(i / 3 - gx[d]) + abs(i % 3 - gy[d]);
    }
    return sum;
}

struct Node {
    int f, g, s;
    bool operator<(const Node& o) const { return f > o.f; } // 小根堆
};

int astar(int start) {
    priority_queue<Node> pq;
    unordered_map<int, int> best;
    best[start] = 0;
    pq.push({hval(start), 0, start});

    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (u.s == GOAL) return u.g;          // 首次弹出即最优
        if (u.g > best[u.s]) continue;          // 过期状态，跳过

        int a[9], pos = 0, t = u.s;
        for (int i = 8; i >= 0; i--) { a[i] = t % 10; t /= 10; if (a[i] == 0) pos = i; }
        int x = pos / 3, y = pos % 3;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
            int np = nx * 3 + ny;
            swap(a[pos], a[np]);
            int ns = 0;
            for (int i = 0; i < 9; i++) ns = ns * 10 + a[i];
            swap(a[pos], a[np]);

            int ng = u.g + 1;
            if (!best.count(ns) || best[ns] > ng) {
                best[ns] = ng;
                pq.push({ng + hval(ns), ng, ns});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    // 预处理每个数字在目标局面中的行列
    int t = GOAL;
    for (int i = 8; i >= 0; i--) { int d = t % 10; t /= 10; gx[d] = i / 3; gy[d] = i % 3; }

    string s; cin >> s;
    int st = 0;
    for (char c : s) st = st * 10 + (c - '0');
    cout << astar(st) << "\n";
    return 0;
}

/* ========== 一、A* ========== */
int h(State s);                        // 必须可采纳：h(s) <= 真实剩余代价

struct Nd { int f, g; State s;
    bool operator<(const Nd& o) const { return f > o.f; } };

int astar(State st) {
    priority_queue<Nd> pq; unordered_map<State,int> best;
    best[st] = 0; pq.push({h(st), 0, st});
    while (!pq.empty()) {
        Nd u = pq.top(); pq.pop();
        if (isGoal(u.s)) return u.g;              // 首次弹出即最优
        if (u.g > best[u.s]) continue;             // 过期状态
        for (State v : nxt(u.s)) {
            int ng = u.g + 1;
            if (!best.count(v) || best[v] > ng) { best[v] = ng; pq.push({ng + h(v), ng, v}); }
        }
    }
    return -1;
}

/* ========== 二、双向 BFS ========== */
int bidBFS(State S, State T) {
    if (S == T) return 0;
    queue<State> q1, q2; unordered_map<State,int> d1, d2;
    q1.push(S); d1[S] = 0; q2.push(T); d2[T] = 0;
    while (!q1.empty() && !q2.empty()) {
        if (q1.size() > q2.size()) { swap(q1,q2); swap(d1,d2); }  // 谁小扩谁
        int sz = q1.size();
        while (sz--) {
            State u = q1.front(); q1.pop();
            for (State v : nxt(u)) {
                int step = d1[u] + 1;
                if (d2.count(v)) return step + d2[v];              // 相遇
                if (d1.count(v)) continue;
                d1[v] = step; q1.push(v);
            }
        }
    }
    return -1;
}

/* ========== 三、迭代加深 / IDA* ========== */
int limit, nxtLimit;

bool dfs(State u, int dep) {
    int f = dep + h(u);                    // 纯迭代加深时把 h(u) 换成 0
    if (f > limit) { nxtLimit = min(nxtLimit, f); return false; }
    if (isGoal(u)) return true;
    for (State v : nxt(u))
        if (dfs(v, dep + 1)) return true;
    return false;
}

int solve(State st, int maxLimit) {
    int lim = h(st);
    while (lim <= maxLimit) {
        limit = lim; nxtLimit = INT_MAX;
        if (dfs(st, 0)) return limit;
        if (nxtLimit == INT_MAX) break;     // 完整展开仍无解
        lim = nxtLimit;                     // 跳到最小超限 f 值
    }
    return -1;
}