/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
H 行 W 列に区切られた盤面があり、盤面の各マスは「表向きのコインが 1 枚置かれている」「裏向きのコインが 1 枚置かれている」「コインが置かれていない」のいずれかです。
また、「1 行目」「2 行目」...「H 行目」「1 列目」「2 列目」...「W 列目」と書かれたカードが 1 枚ずつ合計 W + H 枚あります。
この盤面とこれらのカードを使い、2 人でゲームを行います。
ゲームは、ゲームが終了するまで手番を交互に繰り返します。 各手番は以下の手順で行います。
- 手番プレイヤーはカードを 1 枚自由に選んで取り除く
- 取り除いたカードに書かれた行または列にある全てのコインの裏表を反転させる
- 取り除くカードがなくなった場合、もしくは盤面上の全てのコインが表向きになった場合、ゲームは終了する
ゲーム終了後、各プレイヤーはゲーム終了時の状態に応じて以下の点数を得ます。
- 最後にカードを取り除いたプレイヤーは 1 点を得る
- 盤面上の全てのコインが表向きになっていれば、お互いに 2 点を追加で得る
お互いに自分の得る合計点数を最大化するように最適に行動したとき、先手が得る合計点数を求めてください。
制約
- 1 \leq W, H \leq 2,000
- m_{ij} は
.,o,xのいずれかである - 裏向きのコインが少なくとも 1 枚置かれている
部分点
以下の追加制約を満たすデータセットに正解した場合は、30 点が与えられる。
- 各行には裏向きのコインが少なくとも 1 枚置かれている
- 各列には表向きまたは裏向きのコインが少なくとも 1 枚置かれている
追加制約のないデータセットに正解した場合は、上記とは別に 370 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
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 行で出力せよ。
入力例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
Score : 400 points
Problem Statement
There are a board with H rows and W columns. Each cell on the board is one of the following states: "one coin is placed face up", "one coin is placed face down", or "no coin is placed".
There are also W + H cards and one of the following is written on each card: "Row 1", "Row 2", ..., "Row H", "Column 1", "Column 2", ..., and "Column W". (Each type is written on exactly one card.)
Two players play a game using the board and cards. In this game, two players play their turns alternatingly.
In each turn, one of the players takes the following actions.
- The player removes 1 card he or she wants to.
- When a card is removed, all the coins on the row or column written on the card are turned over.
- The game ends when they have removed all cards or when all the coins are facing up.
When the game ends, the players earn scores according to the final state of the game as follows.
- The player who remove a card last earns 1 point.
- If all the coins are facing up, both players earn 2 points.
Find the total score of the first mover, assuming that both players play optimally to maximize their own scores.
Constraints
- 1 \leq W, H \leq 2,000
- m_{ij} is
.,o, orx - One or more coins are facing down
Partial Scores
30 points will be awarded for passing the test set satisfying the following:
- There are at least one coins facing down on each row.
- There are at least one coins facing up or down on each column.
Another 370 points will be awarded for passing the test set without addtional constraints and you can get 400 points in total.
Input
Input is given from Standard Input in the following format:
m_{ij} represents the state on row i and column j,
., o, and x indicate "no coin is placed", "a coin is placed face up", and "a coin is placed face down", respectively.
H W
m_{11} m_{12} ... m_{1W}
m_{21} m_{22} ... m_{2W}
:
m_{H1} m_{H2} ... m_{HW}
Output
Print the total score of the first mover, assuming that both players play optimally to maximize their own scores.
Sample Input 1
2 5 .x.x. x.o.x
Sample Output 1
3
This input satisfies the additional constraint.
Sample Input 2
7 2 x. xx x. xx x. xx x.
Sample Output 2
3
This input satisfies the additional constraint.
Sample Input 3
4 3 x.o .x. x.x ...
Sample Output 3
1
Sample Input 4
5 1 x o . o x
Sample Output 4
2
Sample Input 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.......
Sample Output 5
3
Sample Input 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.............
Sample Output 6
2