问题 24583 --黑白棋【浙江省选2003】

24583: 黑白棋【浙江省选2003】

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

黑白棋

bw.pas/C/Cpp

规则

    黑白棋(Othello)是由黑方和白方两人进行的益智游戏。棋盘为8x8方格,一般为绿色,黑白棋总共使用64个棋子,每个棋子分正反两面,分别是黑色和白色。开始下棋时,双方各使用32个子,黑方着子时黑面朝上,白方下棋时白面朝上,当一方棋子用完时,另一方应将己方多余的棋子交给对方。
目标

当双方都无棋可下,或者64个方格全部占满后,棋局结束,子多的一方为胜方。

准备开始

在棋局开始前,先把两个黑棋和两个白棋交叉放在棋盘中央,黑子放在e4d5,白子放在d4e5(见图 1)

 

A

B

C

D

E

F

G

H

1

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

4

 

 

 

W

B

 

 

 

5

 

 

 

B

W

 

 

 

6

 

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

1:准备开始

黑方先下,然后双方交替着子。

下棋

轮到一方下棋时,必须把棋下在与对方棋子相邻的空位上,要求所下的棋子和原有的已方棋子夹住对方的至少一个棋子(横竖斜夹均可),然后把被夹住的子变成己方的颜色(也叫吃子)。下棋过程中,任何棋子既不会从棋盘上拿走,也不会从一个格子移到另一个格子。

 

A

B

C

D

E

F

G

H

1

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

4

 

 

 

W

B

 

 

 

5

 

 

 

B

B

B

 

 

6

 

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

以黑棋的第一步下f5为例,f5和原来的d5夹住了白的e5,于是把e5吃掉

 

A

B

C

D

E

F

G

H

1

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

4

 

 

 

W

B

 

 

 

5

 

 

 

W

B

B

 

 

6

 

 

 

W

 

 

 

 

7

 

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

    现在轮到白方下棋,白方有3种选择。当白下f4f6d6时,每种情况都吃掉对方的一个子,注意:上面所说的夹子可以是8个方向中的任意方向,横竖斜均可,并且在任何方向被夹住的子都要被吃掉。

    吃子时,不会发生连锁反应,吃进的棋子不能再夹吃其他的子。

    在轮到你下棋时,如果你无子可吃,你必须停一步,让对方继续下棋,这种情况叫pass;而当你有子可吃时,你不能pass

现在给定一个黑白棋的棋局,问在t步之后,黑方可能占据的最大优势是多少?优势的计算方法是以黑子的数目减去白子的数目。注意,t包括了双方所走步数的总和,pass也算作一步。假设对局永远不结束。

输入文件bw.in开头是一个整数n<=5)表示有几组测试数据。每组测试数据的第一行是正整数t<=4),接下来8行代表了一个合法的黑白棋棋局(这里合法的意思是指能够在实际的对局中出现)。每行8个字符,用B表示黑子,W表示白子,空格表示无子。

对于每组测试数据,在bw.out中输出单独一行一个整数表示在t步之后黑方可能占据的最大优势。

你可以假设对局的双方都不是高手,会走出某些错误的下法使得自己变得十分不利。

 

输入样例:

1

1

 

 

 

   BW

   WB

 

 

 

输出样例:

3

来源

 

[提交][状态]