HDU 2234 無題 I - 4×4 矩陣行列循環移動 IDA* 求最少步數

題目大意

4×4 矩陣，每行/列可循環左/右/上/下移動一格。目標：使某一行全相同或某一列全相同。只需判斷最少步數是否 ≤5，是則輸出步數，否則 -1。T 組測試。

IDA* 設計

• 狀態：4×4 整數矩陣。
• 操作：8 種（4 行 × 左/右 + 4 列 × 上/下）。
• 啟發函數 h：對每行統計「不同數字數 - 1」之和，取行/列兩種方向的最小值，再 (sum + 3) / 4（每步最多修正 4 格）。這是可接受的下界。
• 剪枝：depth + h > limit 回溯；避免逆操作（上一步行左移，本步不嘗試同行右移）。
• 迭代加深：limit = h(initial) 到 5，找到解即返回。

核心代碼 (C++)

#include 
using namespace std;

int grid[4][4];
int limit;
const int dx[4][4] = {{0,1,2,3}, {0,1,2,3}, {0,1,2,3}, {0,1,2,3}}; // 行索引
// 實際操作函數：rowLeft, rowRight, colUp, colDown

int heuristic() {
    int best = INT_MAX;
    // 檢查每行
    for (int i = 0; i < 4; ++i) {
        bool seen[5] = {};
        int diff = 0;
        for (int j = 0; j < 4; ++j)
            if (!seen[grid[i][j]]) { seen[grid[i][j]] = true; ++diff; }
        best = min(best, 4 - diff); // 需統一的數量 = 4 - 不同數
    }
    // 檢查每列
    for (int j = 0; j < 4; ++j) {
        bool seen[5] = {};
        int diff = 0;
        for (int i = 0; i < 4; ++i)
            if (!seen[grid[i][j]]) { seen[grid[i][j]] = true; ++diff; }
        best = min(best, 4 - diff);
    }
    return (best + 3) / 4; // 每步最多改 4 格
}

bool dfs(int depth, int lastOp) { // lastOp 編碼上一步操作，用於逆操作剪枝
    int h = heuristic();
    if (h == 0) return true;
    if (depth + h > limit) return false;

    int backup[4][4];
    memcpy(backup, grid, sizeof(grid));

    // 枚舉 8 種操作，跳過逆操作
    for (int op = 0; op < 8; ++op) {
        if (isReverse(op, lastOp)) continue;
        apply(op); // 修改 grid
        if (dfs(depth + 1, op)) return true;
        memcpy(grid, backup, sizeof(grid)); // 回溯
    }
    return false;
}

int main() {
    int T; cin >> T;
    while (T--) {
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j)
                cin >> grid[i][j];
        for (limit = heuristic(); limit <= 5; ++limit) {
            if (dfs(0, -1)) { cout << limit << '\n'; break; }
        }
        if (limit > 5) cout << -1 << '\n';
    }
    return 0;
}

關鍵點

1. 搜索深度極淺 (≤5)，IDA* 極快，無需複雜狀態編碼/去重。
2. 啟發函數設計巧妙：統一一行/列所需的最少修改格數，除以 4 取上界。
3. 逆操作剪枝大幅減少分支因子（8→6）。

總結

本題展示了 IDA* 在「極淺最優解、分支因子小、狀態易復制」場景下的威力。啟發函數只需是可接受的下界，不必精確。面試中能手寫 IDA* 框架（迭代加深循環 + DFS + 啟發函數 + 剪枝 + 回溯）即為加分項。