UVA 1589 Xiangqi（象棋將軍/將死判定）問題詳解與模擬實現

編輯：關於C語言

UVA 1589 Xiangqi（象棋將軍/將死判定）問題詳解與模擬實現

給定一個合法的象棋殘局：黑方只有將（帥），紅方有將、車、馬、炮（共N≤7子），且紅方已將軍。判斷黑方是否被將死（無任何合法走法解除將軍）。棋盤10×9，坐標(1,1)左上，(10,9)右下。紅方在下方（大x），黑方在上方（小x）。

棋子走法規則（紅方視角，黑方對稱）

將（帥）：九宮格內（x∈[1,3], y∈[4,6]）單步橫縱移動。飛將：雙方將同列且中間無子，可直接捕獲。
車：橫縱任意距離，不能越子。
炮：移動同車；捕獲需隔扣一子（中間恰好一個任意棋子）。
馬：日字腳（8個方向），蹩馬腿：橫/縱方向相鄰點有子則該方向不可走。

判定邏輯

黑將當前位置(x,y)。
枚舉黑將4個合法移動方向（上下左右），以及「不動」（若飛將可捕獲紅將則算解除將軍）。
對每個候選新位置(nx,ny)（含原位），檢查：

bool isSafe(nx, ny) {
    // 1. 九宮格內
    if (nx<1 || nx>3 || ny<4 || ny>6) return false;
    // 2. 臨時移動黑將到(nx,ny)，更新棋盤佔用
    // 3. 檢查是否被紅方任意棋子攻擊：
    //    - 紅將：飛將攻擊
    //    - 紅車/炮/馬：按規則攻擊
    // 4. 若無攻擊，則安全
}

若存在至少一個安全位置，輸出NO（非將死）；否則YES。

C語言參考實現（AC代碼，精簡版）

#include 
#include 

struct Pos { int x, y; };
struct Pos G;            // 紅將
struct Pos R[2], H[2], C[2]; // 紅車馬炮，最多各2個
int rCnt, hCnt, cCnt;
int board[11][10];       // 1-based，1有子

int n, bx, by;           // 黑將位置

// 檢查紅將飛將攻擊 (bx,by)
int checkGeneral(int x, int y) {
    if (G.y != y) return 0;
    for (int i = x+1; i < G.x; ++i)
        if (board[i][y]) return 0;
    return 1;
}

// 車攻擊
int checkChariot(int rx, int ry, int x, int y) {
    if (rx == x) {
        int y1 = ryy?ry:y;
        for (int j = y1+1; j < y2; ++j) if (board[rx][j]) return 0;
        return 1;
    }
    if (ry == y) {
        int x1 = rxx?rx:x;
        for (int i = x1+1; i < x2; ++i) if (board[i][ry]) return 0;
        return 1;
    }
    return 0;
}

// 馬攻擊
int checkHorse(int hx, int hy, int x, int y) {
    // 8個目標相對坐標 & 對應蹩腿點
    const int dx[8] = {-2,-2,-1,-1,1,1,2,2};
    const int dy[8] = {-1,1,-2,2,-2,2,-1,1};
    const int lx[8] = {-1,-1,0,0,0,0,1,1};
    const int ly[8] = {0,0,-1,-1,1,1,0,0};
    for (int k=0;k<8;++k)
        if (hx+dx[k]==x && hy+dy[k]==y)
            return board[hx+lx[k]][hy+ly[k]]==0;
    return 0;
}

// 炮攻擊
int checkCannon(int cx, int cy, int x, int y) {
    if (cx == x) {
        int y1 = cyy?cy:y, cnt=0;
        for (int j=y1+1;jx?cx:x, cnt=0;
        for (int i=x1+1;i=1 && nx<=3 && ny>=4 && ny<=6) {
                board[bx][by]=0; board[nx][ny]=1;
                if (checkSafe(nx,ny)) safe=1;
                board[bx][by]=1; board[nx][ny]=0;
                if (safe) break;
            }
        }
        puts(safe ? "NO" : "YES");
    }
    return 0;
}