日期：2026年11月12日
ZeroJudge 題目連結：o874.搶地棋 (Chess)
題目 pdf 檔連結：搶地棋 (Chess)
解題想法
每組測資第一列為兩個整數 $R, C ~(3 \leq R, C \leq 7)$，代表棋盤的尺寸為 $R \times C$。接下來 $R$ 列、每列有一個長度為 $C$ 的字串，字串中只包含代表棋子的 @ 及代表空地的 #。最多只會有 25 個棋子。玩家 Charlie 先手，Dave 後手。每次行動時要從棋盤上移除符合騎士步的兩個棋子，如果無法移除這樣的棋子則輸掉比賽。由初始盤面狀態預設贏家。
這題考狀態壓縮，因為最多只有 25 個棋子，可以用一個最大為 $2^{25} - 1 = 33554431$ 的整數 $mask$ 代表編號為 $0$ 到 $24$ 的棋子是否在盤面上，如果 $mask$ 第 $i$ 位數為 $1$，代表編號 $i$ 的棋子在盤面上。將各個棋子的坐標存入陣列 $piece$ 之中。用兩層 for 迴圈跑出所有符合騎士步的棋子組合，存入陣列 $masks$ 之中。
這題考的第二個技巧是記憶化 DFS，呼叫自訂函式 dfs 時代入初始盤面狀態 $init$，找出 $init$ 對應的勝負關係。用一個字典或是二維陣列 $memo$ 記錄各種盤面狀態對應的勝負關係。如果用字典記錄狀態，以盤面狀態 $init$ 作為 key 值，如果 $init$ 不在 $memo$ 之中，代表還沒有計算過 $init$ 對應的勝負關係，需要往下遞迴；反之，回傳 $memo[init]$，True 代表目前的玩家必勝，Fasle 代表目前的玩家必敗。遞迴前要先找出下一個狀態 $nxt$，從 $masks$ 之中讀取各種符合騎士步的狀態 $mask$，如果要被移除的兩個棋子在 $init$ 之中，用 XOR 計算出下一個狀態 $nxt$。遞迴，呼叫 $dfs(nxt)$，如果回傳 Fasle，代表下一個行動的玩家必敗，目前的玩家必勝，回傳 True。如果測試完所有的 $mask$ 之後沒有任何遞迴結果為 False，代表目前的玩家必敗，回傳 False。
如果改用二維陣列記錄各種盤面狀態對應的勝負關係，則用 $-1$ 代表還沒有計算過的狀態，$0$ 代表對應的玩家必敗，$1$ 代表目前的玩家必勝。
Python 程式碼
使用時間約為 1.6 s，記憶體約為 265.8 MB，通過測試。
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
# 1. 讀取棋盤及棋子的位置
R = int(data[ptr])
C = int(data[ptr + 1])
ptr += 2
piece = [] # 棋子的位置
for i in range(R):
row = data[ptr]
ptr += 1
for j, c in enumerate(row):
if c == '@':
piece.append((i, j))
# 2. 計算所有符合騎士步規則的狀態
N = len(piece) # 騎子的數量
masks = []
for i in range(N):
for j in range(i+1, N):
dr = abs(piece[i][0] - piece[j][0])
dc = abs(piece[i][1] - piece[j][1])
if (dr == 2 and dc == 1) or (dr == 1 and dc == 2):
masks.append((1 << i) | (1 << j))
# 3. 記憶化 DFS，找出初始狀態 init 對應的勝負關係
memo = [-1] * (1 << N) # -1 沒有，0 敗，1 勝
def dfs(init):
# 遞迴出口，memo 之中有 init 對應的結果，直接回傳
if memo[init] != -1:
return memo[init]
# 測試所有可能的狀態
for mask in masks:
# 如果 init 之中有 mask 要移除的棋子
if (init & mask) == mask:
# 用 XOR 計算新的狀態 nxt
nxt = init ^ mask
# 遞迴，如果 nxt 使對手必敗，則自己必勝，回傳 1
if dfs(nxt) == 0:
memo[init] = 1
return 1
# 測試完畢，沒有觸發第 46 行，自己必敗
memo[init] = 0
return 0
# 4. 呼叫 dfs，代入所有棋子都在盤面上的狀態求解
full_mask = (1 << N) - 1
result.append("Charlie\n" if dfs(full_mask) else "Dave\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
