#29905: 動態規劃


algorithm000@gmail.com (楊名傑)

學校 : 不指定學校
編號 : 190209
來源 : []
最後登入時間 :
2022-04-09 18:41:36
a365. 3. 新井字遊戲 -- 100學年度全國資訊學科能力競賽 | From: [211.72.229.85] | 發表日期 : 2022-04-10 11:52

 

設一陣列takeList,存放所有可拿一步的棋子(單獨一個或連線二個)

用動態規劃完成

answer[4096]儲存所有解

 

將輸入的值轉換成數值,該數值為answer index,answer[index]為解(0或1),預設全為-1

 

初始設定:

將takeList只有一個棋的值在answer內設為0(先手必敗)

將takeList連續二個棋的值在answer內設為1(先手必勝)

 

for將answer每個值填滿

 

依序拿takeList的每步棋,拿了之後的剩下棋局狀態

剩下棋局狀態:

把takeList取1補數再與現在棋局狀態作 &運算

 

去判定之前的answer的狀態,只要為0,就代表這拿法一定贏,將answer設為1

 

之前的answer的狀態如果為1,那就去找尋另一個takeList下法,如果都沒辦法找到,將answer設為1

 

 
ZeroJudge Forum