AT_kupc2017_l.Coin Game 2017
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
有一个 H 行 W 列的棋盘，每个格子的状态可以是以下三种之一：放置了一枚正面朝上的硬币、放置了一枚反面朝上的硬币、没有放置硬币。
同时，我们有 H+W 张卡片，分别标有「第 1 行」、「第 2 行」……「第 H 行」以及「第 1 列」、「第 2 列」……「第 W 列」。
游戏规则如下：利用这些卡片和棋盘，两名玩家轮流进行操作，直到游戏结束。每轮操作包括以下步骤：
- 当前玩家任选一张卡片，并将其移除。
- 将该卡片对应的那一行或那一列中的所有硬币翻转，正面变反面，反面变正面。
- 游戏在以下两种情况下结束：所有卡片都被移除，或棋盘上所有硬币都变为正面朝上。
游戏结束时，玩家的得分规则如下：
- 最后移除卡片的玩家额外得到 1 分。
- 若棋盘上所有硬币都正面朝上，则双方各得 2 额外分。
请计算，当双方都尽可能最大化自己分数时，先手玩家的总得分。
输入格式
输入从标准输入读入，格式为：
$ m_{ij} $ 表示第 i 行第 j 列的状态，.表示该位置没有硬币，o表示该位置有正面朝上的硬币，x表示该位置有反面朝上的硬币。
$ H $ $ W $ $ m_{11} $ $ m_{12} $ $ ... $ $ m_{1W} $ $ m_{21} $ $ m_{22} $ $ ... $ $ m_{2W} $ $ : $ $ m_{H1} $ $ m_{H2} $ $ ... $ $ m_{HW} $
输出格式
输出先手玩家在最优策略下的总得分，结果占一行。
输入输出样例
输入#1
2 5 .x.x. x.o.x
输出#1
3
输入#2
7 2 x. xx x. xx x. xx x.
输出#2
3
输入#3
4 3 x.o .x. x.x ...
输出#3
1
输入#4
5 1 x o . o x
输出#4
2
输入#5
39 40 .........o.............................. .............................o.......... .................o...................... ......o...............................x. ...x......o............................. ...........................o......o..... .........................x.............. .................o.............o........ ..................x..................... .............o.......................... .......................................o ...............o........................ .....x.....o............................ ..................o..................... ..o.........o........................... ...............x........................ .......o............................x... ........................x.....o......... ...................o.........o.......... ........x..........................o.... ......................o...o............. ..............o..................o...... ..............x......................... x....................................... ..o....................x................ .........................o.............. .o...................................o.. .................................o...... .o..................x................... ...........o....o....................... .............x.......................... ...............................x........ ....o..............................o.... ..........................o.x........... ...................x.................... .....................................o.. .........x.............................. o......................................o .....................x..........o.......
输出#5
3
输入#6
38 39 .......o............................x.. .........x............................. ................x...................... ............x.......................... .................x..........o.......... ..................................o..o. ...............................o....... .....................x..........o...... .............o......................... ..o....................o............... ....x.................................. ...................o................... ..................o.................... .....x.....o........................... .o..................o.................. ....................o......x........... .........................o............. ..................x.................... ...............o....................... ......o...............................x .......................o.........x..... ...............x....................... .o..................................... .........o............................. o...................................... ..............o.......o................ ............o......o................... ........o..........................o... ..........................o.o.......... ...x......o............................ ......................x................ .............x......................... o...o.................................. ........o....................x......... ..............o........................ ................o..............o....... ........................x.....o........ .........................x.............
输出#6
2
说明/提示
- $ 1 \leq W, H \leq 2,000 $
- $ m_{ij} $ 表示为
.,o,x之一 - 至少存在一个反面朝上的硬币
部分分数
对于符合下列额外条件的数据集，正确解答可获得 30 分：
- 每行至少有一个反面朝上的硬币。
- 每列至少有一个正面或者反面朝上的硬币。
不受额外条件限制的数据集正确解答可获得 370 分。
样例说明 1 & 2
此样例满足额外条件。
本翻译由 AI 自动生成
输入解题思路，AI测评打分。不知道怎么写?