P10645: 博弈
传统题
1.000s
时间限制
128MB
内存限制
0 提交
0 解决
【题目描述】
【问题描述】
小智和童童最近在玩黑白棋！ 黑白棋规则如下：
1、游戏使用标准的8×8棋盘，上面初始时有四枚棋子：两枚黑色棋子和两枚白色棋子，按照对角线交叉排列。
2、
游戏开始时，黑方先行。
3、玩家的目标是通过翻转对手的棋子，将棋盘上的大多数格子占为己有。
4、每一步，玩家必须将自己的棋子放在一个合法的位置上。合法的位置必须满足以下条件：
-
新放置的棋子必须与棋盘上已有的同色棋子在一条直线（水平、垂直或对角线）上夹住对方的一串棋子（夹住的意思是，在夹住的一端是己方的棋子，另一端是对方的棋子）。
-
在夹住对方棋子的同时，所有被夹住的对方棋子都会被翻转成己方颜色。
5、
如果某一方无法合法落子，则该回合轮到对方继续行动。
6、
游戏继续进行，直到棋盘被填满或双方都无法合法落子。
7、游戏结束时，棋盘上棋子数较多的一方获胜。如果双方棋子数相同，则为平局。
给定一个n×n
棋盘上的黑白棋残局，对于接下来所有的可能局面——也就是说，黑方白方轮流行棋，白方先行，走到双方都无法行棋，在所有的可能状态中，最终黑方获胜的有多少种，白方获胜的有多少种，平局有多少种。
在本题中，我们定义残局为最多有不超过10个未被放入棋子的格子。
需要注意的是：我们给出的棋盘不一定能够从一个合法的开局得到。你无需关心当前棋盘局面是如何形成的——即便它并不连通。
【输入格式】
第一行，一个整数n，表示这个棋盘的大小是n×n
。
接下来n行，每行n
个整数，表示棋盘。如果这个数是0，表示这里是白子，如果这个数是1，表示这里是黑子，如果这个数是−1，表示这里是空的。
【输出格式】
一行，三个整数，黑方胜利的状态数，白方胜利的状态数，平局的状态数。
【输入样例一】
3
-1 0 1
0 1 0
1 0 -1
【输出样例一】
2 0 0
【输入样例二】
4
-1 -1 -1 -1
-1 0 1 0
-1 1 0 1
-1 -1 -1 -1
【输出样例二】
1813 2494 519
【约定和数据范围】
数据点1∼6，1≤n≤3，空格子数不超过4
。
数据点7∼12，1≤n≤4，空格子数不超过5
。
数据点13∼18，1≤n≤4，空格子数不超过10。
数据点19∼23，1≤n≤5，空格子数不超过5。
数据点24∼25，1≤n≤5，空格子数不超过10。
【输入】
第一行，一个整数n，表示这个棋盘的大小是n×n。
接下来n行，每行n个整数，表示棋盘。如果这个数是0，表示这里是白子，如果这个数是1，表示这里是黑子，如果这个数是−1，表示这里是空的。
【输出】
一行，三个整数，黑方胜利的状态数，白方胜利的状态数，平局的状态数。
【样例输入】复制
3
-1 0 1
0 1 0
1 0 -1