黑白棋I

时间限制: 10 ms 内存限制: 5000 kb
总通过人数: 3 总提交人数: 4

题目描述

黑白棋是一种两人对弈的游戏,一人执黑子,一人执白子。所用的棋盘为8×8,开盘时,棋盘上正中共有4粒棋子,呈对角线排列,两白两黑,由执黑者先行。
黑白棋的走法关键在于"夹"字,无论黑白哪方,都必须将棋子下在夹住对方的棋子的地方。其夹法可以采用直线、斜 线,下在其它地方均属非法,系统将不允许落子。
被对方棋子夹住的棋子,会"投降"变成对方的棋子。同样的,不论直线斜线,只要被对方的棋子夹住,都会"投降"。 因此,你一定要落子巧妙,就可以用最少的棋子夹住最多的棋。
若有一方没有地方可以合法落子,则系统会自动跳过,由对方走。
获胜有两种情况:
当棋盘下满或双方都无棋可走时,谁的棋子多,谁获胜。
当一方将对方的全部棋子俘虏时该方获胜。
若棋盘下满或双方都无棋可走时,双方棋子数目相同,则和棋。
我们来举一个栗子:
下图是开局情况,执黑先行:

如下图,透明黑子为可能的走法

下完黑棋后,按照规则,黑棋与其它黑棋之间的直线(水平,竖直或对角)上的白子都会变成黑子,这些棋子之后可为黑棋所用,即被对方棋子“夹”住的棋子,会“投降”变成对方的棋子——除非白子又把它们变了回来。换句话说,一个有效的落子必须反转至少一个对方的棋子。
如果黑子下在上面的位置,位于d4的白子被反转 :


然后白棋下。按照相同的规则,白棋落子,反转位于d5的黑棋。下图,透明白子为可能的走法

白子落在左下角,反转位于d5的黑棋

按照上述规则,双方交替进行,如果一方没有地方可以合法落子,则跳过,由对方走。当棋盘下满或一方都无棋可走或双方无法均合法落子时,游戏结束。 现在经过几轮之后,黑棋下。你可以求出最大能反转几颗白子吗?

输入

第一行输入一个整数T表示数据组数
每组数据有8行,每行8个字符,(D代表黑棋,L代表白棋,*代表没有棋子) 相邻的两组数据之间有一个空行

输出

每组数据,输出第几组数据和最大能反转的白子数,如果没有地方可以合法落子,输出0 请按照样例输出的格式输出

输入样例

3
********
********
********
***LD***
***DL***
********
********
********

********
********
**DLL***
**DLLL**
**DLD***
********
********
********

********
********
*D******
*DLLD***
***LL***
**D*D***
********
********

输出样例

Case 1: 1
Case 2: 3
Case 3: 0

Hint

TLE的同学注意使用scanf,同时对代码进行优化
MLE的同学注意数组的类型及大小,省去不必要的递归
WA的同学注意特殊情况
RE的同学仔细检查数组越界
学长只能帮你到这了
powered by microhhh——冬藏,期待春生

相关推荐