您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1813 Escape from Tetris - IDA* 找最短通用逃生指令序列

編輯：關於C++

題目大意

給定 N×N (N<9) 棋盤，0 為可通行，1 為障礙。Lele 可能被放在任意一個 0 格。需找一個最短指令序列（由 north/east/south/west 組成），使得無論起始位置為何，按序執行指令（遇障礙或邊界忽略該指令）最終都能走到邊界（即逃脫）。若有多解，輸出字典序最小者。

關鍵觀察

這是一個多起點同步規劃問題：同一指令序列必須對所有可達狀態同時生效。
狀態可表示為「所有可能位置的集合」。初始狀態 = 所有 0 格。每條指令將集合中每個位置嘗試移動，合併結果（去重）。
目標狀態 = 所有位置均在邊界上（或已逃脫）。
狀態空間上限：2^(N×N) ≤ 2^64，但實際可達狀態極少，適合 IDA*。

IDA* 設計

啟發函數 h(s)：對當前集合中每個位置計算其到最近邊界的曼哈頓距離（忽略障礙），取最大值。因為所有位置必須同時逃脫，最慢的那個決定了下界。
剪枝：depth + h > limit 直接回溯。
字典序：按 east, north, south, west 顺序嘗試方向（題目要求字典序最小）。
去重：用 bitset 或 64 位整數表示位置集合，配合 visited 表（或深度限制下的路徑檢查）避免循環。

核心代碼框架 (C++)

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

const int dx[4] = {0, -1, 1, 0};  // east, north, south, west
const int dy[4] = {1, 0, 0, -1};
const char* dirName[4] = {"east", "north", "south", "west"};

int N, limit;
uint64_t startMask, goalMask; // 用 64 位整數表示位置集合 (N≤8 → 64 格)
int dist[8][8];               // 每格到最近邊界的曼哈頓距離

int heuristic(uint64_t mask) {
    int h = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (mask & (1ULL << (i*N + j)))
                h = max(h, dist[i][j]);
    return h;
}

bool dfs(uint64_t mask, int depth, int lastDir) {
    int h = heuristic(mask);
    if (h == 0) return true;           // 所有位置已在邊界
    if (depth + h > limit) return false;

    for (int d = 0; d < 4; ++d) {
        if (d == (lastDir ^ 1)) continue; // 簡單逆操作剪枝：0↔1, 2↔3
        uint64_t next = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (mask & (1ULL << (i*N + j))) {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (ni < 0 || ni >= N || nj < 0 || nj >= N || board[ni][nj] == '1') {
                        next |= 1ULL << (i*N + j); // 撞牆/障礙，原地不动
                    } else {
                        next |= 1ULL << (ni*N + nj);
                    }
                }
        if (dfs(next, depth + 1, d)) {
            path[depth] = d;
            return true;
        }
    }
    return false;
}

int main() {
    while (cin >> N) {
        // 讀棋盤，計算 startMask、dist、goalMask
        // 迭代加深
        for (limit = heuristic(startMask); ; ++limit) {
            if (dfs(startMask, 0, -1)) break;
        }
        // 輸出 path[0..limit-1] 對應的方向名
    }
}