這個(gè)題目來自TopCoder SRM 534 Div1 250分的題目 EllysCheckers全闷。
原題
EllysCheckers
題意
2個(gè)人玩游戲，這個(gè)棋盤游戲是一個(gè)1*n的棋盤潘鲫，每個(gè)位置上最多一個(gè)子翁逞。然后有兩種不同的操作方式：
- 選擇其中一個(gè)子往右邊移動(dòng)一步（右邊的位置是空的）
- 選擇一個(gè)子往右邊移動(dòng)3步（右一右二有棋子，右三沒有）
當(dāng)一個(gè)棋子到達(dá)最優(yōu)邊時(shí)溉仑，就立刻消失挖函。
無路可走的人失敗，現(xiàn)在給一個(gè)初始棋盤浊竟，問先手能否必勝怨喘。（假設(shè)兩個(gè)人都是絕對(duì)聰明的玩家）
數(shù)據(jù)范圍是20
思路
一道題上來我們先看數(shù)據(jù)范圍津畸，范圍是20，棋盤有兩種狀態(tài)必怜，這意味著我們能夠枚舉出所有棋盤的狀態(tài)(2^20)洼畅。
我們把棋盤的每個(gè)狀態(tài)稱之為局面，兩個(gè)絕對(duì)聰明的人博弈有下面這么一個(gè)原則：
- 每個(gè)局面不是必勝態(tài)棚赔，就是必?cái)B(tài)帝簇。（兩個(gè)人都會(huì)選擇最優(yōu)的結(jié)果）
- 如果能下一步是一個(gè)必?cái)B(tài)，那么這個(gè)局面是必勝的靠益。
- 如果一個(gè)局面只能到達(dá)必勝態(tài)丧肴，那么，這個(gè)是必?cái)〉摹?/li>
在本題中胧后，如果只有一個(gè)棋子芋浮，并且這個(gè)棋子在最右邊，或者一個(gè)棋子都不存在壳快，則為必?cái)B(tài)。
我們可以用一個(gè)map來記錄這個(gè)狀態(tài)眶痰，然后開始記憶化搜索。
我們注意到這個(gè)題目還有另外一個(gè)條件竖伯，當(dāng)棋子到達(dá)最右的時(shí)候消失存哲，這個(gè)條件等價(jià)于最右的位置可以放多個(gè)棋子七婴。
關(guān)鍵代碼(JAVA)
private boolean canWin(int board, int length){
if (map.containsKey(board)){
return map.get(board);
}else{
//能夠到達(dá)必?cái)B(tài)的一定是必勝態(tài), 到達(dá)不了必勝態(tài)的, 就是必?cái)B(tài).
boolean reachLoseGame = false;
//像右移動(dòng)一位
for (int i = length - 1; i > 0; --i){
if (isChess(board, i)){
//右邊沒棋子或者右邊是最后一位
if (i - 1 == 0 || !isChess(board, i - 1)){
if (!canWin(board ^ (1 << i) | (1 <<(i - 1)), length)){
reachLoseGame = true;
}
}
//右邊兩個(gè)棋子,并且第3位為空格 或者 是最后一位
if (i > 2 && isChess(board, i - 1) && isChess(board, i - 2)){
if (i - 3 == 0 || !isChess(board, i - 3)){
if (!canWin(board ^ (1 << i) | (1 << (i - 3)), length)){
reachLoseGame = true;
}
}
}
}
}
map.put(board, reachLoseGame);
return reachLoseGame;
}
}
