U269106 ZJOI2003 黑白棋

ZJOI2003    

## 规则 黑白棋(Othello)是由黑方和白方两人进行的益智游戏。棋盘为8x8方格，一般为绿色，黑白棋总共使用64个棋子，每个棋子分正反两面，分别是黑色和白色。开始下棋时，双方各使用32个子，黑方着子时黑面朝上，白方下棋时白面朝上，当一方棋子用完时，另一方应将己方多余的棋子交给对方。 ## 目标 当双方都无棋可下，或者64个方格全部占满后，棋局结束，子多的一方为胜方。 ### 准备开始 　　在棋局开始前，先把两个黑棋和两个白棋交叉放在棋盘中央，黑子放在e4和d5，白子放在d4和e5(见图 1)。 1.jpg 图1：准备开始 黑方先下，然后双方交替着子。 ### 下棋 　　轮到一方下棋时，必须把棋下在与对方棋子相邻的空位上，要求所下的棋子和原有的已方棋子夹住对方的至少一个棋子(横竖斜夹均可)，然后把被夹住的子变成己方的颜色(也叫吃子)。下棋过程中，任何棋子既不会从棋盘上拿走，也不会从一个格子移到另一个格子。 2.jpg 　　　以黑棋的第一步下f5为例，f5和原来的d5夹住了白的e5，于是把e5吃掉 现在轮到白方下棋，白方有3种选择。当白下f4、f6或d6时，每种情况都吃掉对方的一个子，注意：上面所说的夹子可以是8个方向中的任意方向，横竖斜均可，并且在任何方向被夹住的子都要被吃掉。 吃子时，不会发生连锁反应，吃进的棋子不能再夹吃其他的子。 3.jpg 在轮到你下棋时，如果你无子可吃，你必须停一步，让对方继续下棋，这种情况叫pass；而当你有子可吃时，你不能pass。 现在给定一个黑白棋的棋局，问在t步之后，黑方可能占据的最大优势是多少？优势的计算方法是以黑子的数目减去白子的数目。注意，t包括了双方所走步数的总和，pass也算作一步。假设对局永远不结束。

输入文件bw.in开头是一个整数n（

对于每组测试数据，在bw.out中输出单独一行一个整数表示在t步之后黑方可能占据的最大优势。 　　你可以假设对局的双方都不是高手，会走出某些错误的下法使得自己变得十分不利。

数据范围：$n