atcoder#ACL1C. Moving Pieces
Moving Pieces
Score : points
Problem Statement
There is a board with rows and columns. The information of this board is represented by strings . Specifically, the state of the square at the -th row from the top and the -th column from the left is represented as follows:
.
: the square is empty.#
: an obstacle is placed on the square.o
: a piece is placed on the square.
Yosupo repeats the following operation:
- Choose a piece and move it to its right adjecent square or its down adjacent square. Moving a piece to squares with another piece or an obstacle is prohibited. Moving a piece out of the board is also prohibited.
Yosupo wants to perform the operation as many times as possible. Find the maximum possible number of operations.
Constraints
- is a string of length consisting of
.
,#
ando
. - the number of pieces .
In other words, the number of pairs that satisfy
o
is between and , both inclusive.
Input
Input is given from Standard Input in the following format:
Output
Print the maximum possible number of operations in a line.
3 3
o..
...
o.#
4
Yosupo can perform operations times as follows:
o.. .o. ..o ... ...
... -> ... -> ... -> ..o -> ..o
o.# o.# o.# o.# .o#
9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#
24