← 返回题目列表

AtCoder · kupc2017_l

L. 金币游戏2017

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一块板 H 行和 W 列。板上的每个单元格都处于以下状态之一:“一枚硬币面朝上放置”、“一枚硬币面朝下放置”或“没有放置硬币”。

还有 W + H 卡,每张卡上写有以下内容之一:“行 1“,”行 2“,...,”行 H“,”列 1“,”列 2“,...,和”列 W“。 (每种类型都写在一张卡片上。)

两名玩家使用棋盘和纸牌玩游戏。 在这个游戏中,两名玩家轮流玩。

在每个回合中,其中一名玩家会采取以下行动。

  • 玩家移除 1 他或她想要的卡。
  • 当一张卡片被取出时,卡片上所写的行或列上的所有硬币都会被翻转。
  • 当他们取出所有牌或所有硬币都面朝上时,游戏结束。

当游戏结束时,玩家根据游戏的最终状态获得分数,如下所示。

  • 最后移除一张牌的玩家将获得 1 点。
  • 如果所有硬币都面朝上,则双方玩家均可获得 2 点。

假设两个玩家都以最佳方式发挥自己的得分最大化,求出先行者的总得分。

约束

  • 1 \leq W, H \leq 2,000
  • m_{ij} is ., o,或 x
  • 一枚或多枚硬币面朝下

部分分数 通过满足以下条件的测试集将获得

30 积分:

  • 每行至少有一枚面朝下的硬币。
  • 每列至少有一枚朝上或朝下的硬币。

另一个 370 在没有额外限制的情况下通过测试集将获得积分,您可以获得 总共 400 点。


输入

输入由标准输入按以下格式给出:

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