HDU 4528: 馬拉松 - 狀態 BFS 最短步數

問題描述

網格地圖，有車、馬、炮三枚己方棋子（走法同中國象棋），敵方將軍和士兵（靜止）。求最少步數殺死將軍。棋子可重複經過同一格，但狀態（三子位置）不可重複。

狀態設計

狀態 = (車x, 車y, 馬x, 馬y, 炮x, 炮y)。每子最多 10×10 位置，狀態數 ≤ 10⁶，用 6 維 bool 數組或哈希去重。
BFS 展開：每步移動一枚棋子，生成新狀態入隊。判斷殺將：車/炮同行/列且中間無阻擋（含另兩子）；馬走「日」字且無蹩腿。

優化要點

• 預計算馬的 8 個相對移動及蹩腿判斷。
• 車/炮射線檢測中間障礙物。
• 狀態數組開 [11][11][11][11][11][11] 稍大，實際可用 unordered_set 或壓縮編碼。