BUPT 240. Three Kingdom Chess

Brief description:

諸葛亮和周瑜兩個人正在玩曹操傳。。
(反正就是某種戰棋遊戲。。。具體規則請參見題目。。)

Analysis:

Bug fixed : Orz 。。原來是對於移動後不攻擊的操作符。。我的程序里認為它 delta 為 0 所以仍然按照一般的操作符處理,但是它會將 O[][] 數組錯誤覆蓋掉。。。
(用來表示某個格子處棋子所屬的。。)。。

前排膜拜這位仁兄的代碼。。

Note : 調整搜索的順序對 Alpha-beta 剪枝也會有效,我採用的是用這一步所造成的傷害作為第一關鍵字,這一步移動的距離作為第二關鍵字進行結點排序,
(。。感到這一步還可以往下搜若干個估價層。。然後用後幾部的傷害、距離作為關鍵字。。。實際可能還需要設置一個 threshold 。。)

Test:

// Input 0: 。。。這組數據返回多少?
// Input 1: 敵方一名弓箭手佔據地圖中央的一塊高地。。需要控制我方戰車沿最佳路線躲避。。
// Input 2~3: 步兵和戰車在一塊開闊地帶展開拉鋸。。

Input 0:
3 3 5
0 2 2
2 0 2
2 2 0
3 1 1 1
1 1 0 1 1
2 2 1 10 0
3 3 0 100 2

0 0 0

Output 0:
91 91.5 86.75 87.25 82.75 83.25 79 79.5 75.5 76 71.5
91 91 86 86 81 81 76 76 71 71 66

Input 1:
5 5 10
0 0 0 0 1
0 0 2 2 0
0 2 0 0 2
0 0 2 2 0
0 0 0 0 0
2 1 1 1
3 4 1 1 1
1 4 0 100 2

0 0 0

Output 1:
99 99 97 97 97 97 97 97 97 97 97

Input 1:
5 5 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 1 0 2
1 1 0 1 1
3 5 1 4 0

5 5 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 1 0 2
1 1 0 100 1
3 5 1 2 0

0 0 0

Output 2:
-3 -3 -3 -3 -3 -3 -3 -3 -4 -4 -4
98 98 98 98 98 98 98 98 97 97 96

External link:

http://boj.me/onlinejudge/newoj/showProblem/show_problem.php?problem_id=240
http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://blog.renren.com/blog/282892548/773158465