分数: 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