題目簡述
10×9 棋盤，僅含黑將、紅將、紅車/砲/馬。紅方已將軍，判斷黑方是否被將死（無合法走法解除將軍）。
核心解題步驟
- 建模棋盤與棋子：用結構體儲存型別、顏色、座標；建立 10×9 陣列索引棋子指標。
- 實作各棋子走法與攻擊判定：
- 將：九宮內單步直走；飛將規則（同檔無阻隔可直取）。
- 車：直線任意距離，不可越子。
- 砲：移動同車，吃子需恰好隔一子（架砲）。
- 馬：日字腿，受蹩馬腿限制（橫/直相鄰點有子則該方向不可走）。
- 判定「被將軍」來源：枚舉所有紅方棋子，檢查是否攻擊到黑將位置。
- 生成黑方所有合法應著：
- 黑將嘗試 4 方向移動（含飛將捕捉紅將）。
- 若有其他黑棋（本題無），嘗試攔截/捕捉將軍來源棋子。
- 模擬應著後局面：對每個候選走法，執行移動，檢查黑將是否仍被攻擊。若存在任一走法使黑將安全 → 輸出 "NO"，否則 "YES"。
關鍵優化
- 預計算各棋子攻擊位元組/查表，加速「是否被攻擊」查詢。
- 利用對稱性減少重複計算。
- 測試資料 ≤ 40 組，單組狀態空間極小（≤7 紅棋），暴力模擬完全在 1 秒內。
參考資源
- HDU 1848 / POJ 1848 / ZOJ 2084 "Xiangqi"
- GitHub 搜尋 "Xiangqi checkmate" 可找到 C++/Java 參考實作。
結語
將死判定本質是「單步博弈樹搜尋深度 1」。把規則翻譯成無誤的程式碼，比演算法優化更關鍵。建議先寫「棋子攻擊判定」單元測試，再組裝主流程。
