CCF认证201803-4棋局评估如何通过长尾关键词优化？

本文共计1211个文字，预计阅读时间需要5分钟。

CCF认证，201803-4，棋局评估，思路：对抗搜索，参考：dfs，搜索界面保存最大最小值，参考博客，问题描述：Alice和Bob正在玩井字棋游戏。井字棋规则简单。

CCF认证201803-4 棋局评估

思路：博弈对抗搜索，​​参考​​​，dfs，搜索局面分情况保存最大最小值，​​参考博客​​

问题描述

　　Alice和Bob正在玩井字棋游戏。

　　井字棋游戏的规则很简单：两人轮流往3*3的棋盘中放棋子，Alice放的是“X”，Bob放的是“O”，Alice执先。当同一种棋子占据一行、一列或一条对角线的三个格子时，游戏结束，该种棋子的持有者获胜。当棋盘被填满的时候，游戏结束，双方平手。

　　Alice设计了一种对棋局评分的方法：

　　- 对于Alice已经获胜的局面，评估得分为(棋盘上的空格子数+1)；

　　- 对于Bob已经获胜的局面，评估得分为 -(棋盘上的空格子数+1)；

　　- 对于平局的局面，评估得分为0；

　　例如上图中的局面，Alice已经获胜，同时棋盘上有2个空格，所以局面得分为2+1=3。

　　由于Alice并不喜欢计算，所以他请教擅长编程的你，如果两人都以最优策略行棋，那么当前局面的最终得分会是多少？

输入格式

　　输入的第一行包含一个正整数T，表示数据的组数。
　　每组数据输入有3行，每行有3个整数，用空格分隔，分别表示棋盘每个格子的状态。0表示格子为空，1表示格子中为“X”，2表示格子中为“O”。保证不会出现其他状态。