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

AOJ 0121 Seven Puzzle - 廣度優先搜索求最少移動步數

編輯：關於C++

問題描述

有一個 2×4 的拼圖板（共 8 個格子），數字 0-7 各佔一格，0 代表空格。每次可將上下左右相鄰的數字移動到空格位置。給定初始狀態，求到達目標狀態 0 1 2 3 4 5 6 7 的最少移動步數。

範例： 1 0 2 3 4 5 6 7 → 僅需 1 步（0 和 1 交換）

解題思路：BFS 預計算所有狀態

狀態空間較小（8! = 40,320），可從目標狀態反向 BFS 預計算所有狀態到目標的最短距離，查詢時 O(1) 回答。

關鍵實現細節

狀態編碼：用 8 字符字符串表示（如 "01234567"）
移動方向：dx = {1, -1, 4, -4} 對應右、左、下、上
邊界檢查：排除第 3→4、4→3 列的非法左右移動
訪問記錄：map dist 存儲步數

C++ 完整代碼

#include 
#include 
#include 
#include 
using namespace std;

const int dx[4] = {1, -1, 4, -4};
map dist;

void bfs() {
    queue q;
    string target = "01234567";
    q.push(target);
    dist[target] = 0;
    
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        int pos = cur.find('0');
        
        for (int d = 0; d < 4; ++d) {
            int np = pos + dx[d];
            // 邊界檢查：排除 3↔4 列的橫向移動
            if (np < 0 || np >= 8) continue;
            if (pos == 3 && d == 0) continue; // 3→4 非法
            if (pos == 4 && d == 1) continue; // 4→3 非法
            
            string nxt = cur;
            swap(nxt[pos], nxt[np]);
            if (!dist.count(nxt)) {
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
        }
    }
}

int main() {
    bfs(); // 預計算所有狀態
    
    int x;
    while (true) {
        string s;
        for (int i = 0; i < 8; ++i) {
            if (!(cin >> x)) return 0;
            s += char('0' + x);
        }
        cout << dist[s] << endl;
    }
    return 0;
}