# Moving Pieces SOLUTIONS ACL CONTEST 1

Page Contents

## Moving Pieces SOLUTION

Issue Statement
There is a board with
N
lines and
M
sections. The data of this board is spoken to by
N
strings
S
1
,
S
2
,
,
S
N
. In particular, the condition of the square at the
I
– th line from the top and the
j
– th section from the left is spoken to as follows:
S
I
,
j
=
. : the square is unfilled.
S
I
,
j
=
# : a snag is put on the square.
S
I
,
j
=
o : a piece is set on the square.
Yosupo rehashes the accompanying activity:
Pick a piece and move it to its privilege adjecent square or its down nearby square. Moving a piece to squares with another piece or an impediment is restricted. Moving a piece out of the board is likewise restricted.
Yosupo needs to play out the activity whatever number occasions as could reasonably be expected. Locate the most extreme conceivable number of activities.
Imperatives
1
N
50
1
M
50
S
I
is a line of length
M
comprising of ., # and o.
1
(
the quantity of pieces
)
100
. As such, the quantity of sets
(
I
,
j
)
that fulfill
S
I
,
j
=
o is between
1
furthermore,
100
, both comprehensive.
Info
Info is given from Standard Input in the accompanying organization:
N
M
S
1
S
2
S
N
Yield
Print the most extreme conceivable number of activities in a line.
Test Input 1
Duplicate
3
o..
o.#
Test Output 1
Duplicate
4
Yosupo can perform activities
4
times as follows:
o.. .o. ..o … …
… – > … – > … – > ..o – > ..o
o.# .o#
Test Input 2
Duplicate
9 10
.#….o#..
.#..#..##o
…..#o.##
.###.#o..o
#.#…##.#
..#..#.###
#o…..#..
….###..o
o…….o#
Test Output 2
Duplicate
24