UOJ Logo

NOI.AC

1S 64MB

#714. 井子棋

Statistics

时间:1秒 空间:64MB

题目描述

井子棋是一个十分简单的游戏。双方在3×3的网格上对弈。在本题中,每个格子可能是以下状态之一:

  • .表示此处为空,没有棋子。
  • o表示此处有一颗先手的棋子。
  • x表示此处有一颗后手的棋子。

初始时,棋盘上可能已经有一些棋子了。游戏的流程是,从先手开始,双方轮流向棋盘上摆放一颗自己的棋子,直到棋盘上不存在空地为止。

如果某个玩家的3颗棋子连成一条直线,则这位玩家会获得1分;如果有多个这样的情况发生,则得分累加。游戏结束后,先手获得的总价值为自己的分数减去后手的分数。当然,先手会尽可能最大化这一价值,而后手会尽可能最小化之。

给出初始的棋盘,假定双方都采取最优策略,请问先手能够获得多少价值?

输入格式

每个输入文件有多个数据。第一行输入该文件的数据个数。

接下来依次输入每个数据。每个数据的第一行为空行,接下来三行中每行有三个字符,为.ox之一,表示初始时的棋盘。

输出格式

对于每个数据输出一行,包含一个整数,表示先手能获得的价值。

样例输入

3

ooo
xxx
ooo

o.o
.o.
o.o

x..
...
..x

样例输出

1
4
0

数据范围

同一个测试点中,保证不存在多个相同的输入数据。

本题共10个测试点,每个测试点10分。对于第i个测试点,其中的所有数据满足初始时棋盘恰好有i-1个空地。