e002: 兵臨城下

e002: 兵臨城下

題 意:

OpenChan 再 次 向 Kitty 挑 戰，這 次 玩 得 遊 戲 是 "兵 臨 城 下"，如 下 圖 所 示，每 個 獨 立 的 列 有 20 格，共 有 N 列，在 每 列 之 上 置 有 雙 方 棋 子 各 一 顆 ( 橘 色 在 左，綠 色 在 右 )，每 次 旗 子 可 以 向 左 或 向 右 移 動 1～M  步，但 不 可 超 越 ( 或 重 疊 ) 對 方 棋 子。由 OpenChan 選 定 橘 色 棋 子 並 先 走，兩 人 輪 流 移 動 棋 子，最 後 一 人 如 果 已 無 法 移 動 任 何 己 方 的 旗 子 時，則 輸 了 這 盤 棋。
兩 人 再 次 使 出 了 洪 荒 之 力，請 問 最 後 誰 會 獲 勝？

solve:
傳 說 中 的 sg 函 式。
定 義 兩 棋 子 間 隔 的 格 子 數 為 一 局 面 的 特 徵 值，然 後 遞 推 並 照 sg 的 定 義 去 做 就 好 了 (找 沒 出 現 的 最 小 非 負 整 數 特 徵 值)，再 對 每 個 局 面 都 做 xor 運 算，大 於 1 是 先 手 必 勝，反 之。

code :