poj1741，POJ - 1704 Georgia and Bob

Georgia and Bob

題意：

• 一個水平網格上有N個棋子
• Georgia和Bob每到自己回合時可以向左移動網格上任意一個棋子任意步數
• 棋子與棋子之間不能重疊和相互跨越
• 當到對手回合時，其無法再移動任何棋子則我方贏
• 假設Georgia和Bob都采用最優策略，誰會贏得比賽？

poj1741、輸入要求：

• 第一行依次輸入網格上所有棋子所在的位置，如：1 3 6 7
• 第二行輸入先手者的名字，如：Georgia

輸出要求：

• 如果Georgia贏的比賽，輸出：“Georgia will win”
• 如果Bob贏的比賽，輸出：“Bob will win”

思路：

• 把該問題類比Nim游戲
• 每兩個棋子：看作一個石堆，如上圖中1和3看作一個石堆，6和7看作一個石堆，如果棋子個數為奇數個，那么首個棋子與網格的邊界作為一個石堆
• 棋子之間的空格數量：看作石堆中的石子數量
• 任意一個棋子向左移動任意步數：看作從任意一個石堆中取出任意數量石子
• 只需要判斷所有的初始石堆(所有的每兩個一組的棋子)，相應石子數量(每組棋子中間的空格數量)的異或結果是否為0即可

解釋一下為什么上圖中3和6之間的空格不做考慮：因為如果雙方均采用最優策略，那么即便移動6，下一個回合對手肯定要移動7來跟進6，保證了6和7之間的空格不會改變，最終結果就是3和6會靠在一起，兩個為一組的棋子之間的空格沒有改變。