405115: GYM101798 J Complete the Square

Complete the Square is a two-player game played on a grid of R rows, each containing C dots.

In one turn, a player draws a vertical or a horizontal segment between two adjacent dots. This segment has to be new (not drawn before).

A square is completed if its four sides are drawn. When a player completes a square, they write the first letter of their name in that square and receive one point. After completing a square, the same player has to draw another segment unless the grid is completed.

As shown in the image, in one turn, player B completed 5 squares and drew an extra segment. The numbers written in the squares are for clarifying the order in which the squares were completed. Note that it is possible that a player completes two squares at the same moment.

Given a state of the game, find the maximum number of squares you can complete in one turn.

The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and columns of the grid.

Each of the following 2R - 1 rows contains 2C - 1 characters representing the state of the game. Since the letter in each square is irrelevant for solving the problem, a completed square will contain the lowercase English letter 'x'.

A vertical segment is represented with a vertical bar '|', a horizontal segment is represented with a dash '-'. Dots are represented with the lowercase English letter 'o'. Edges that are not drawn or squares that are not completed will be represented with a dot '.'.

It is guaranteed that the input is valid in a way that every completed square is filled with an 'x', and every uncompleted square is filled with a dot '.'. No character will appear in an invalid place (for example, no '|' will appear in the place of a horizontal segment).

The given state of the game is not necessarily reachable through valid sequence of turns. However, consider it as an initial state for the game and solve the problem.

Print the maximum number of squares you can complete in one turn.

5 6
o-o.o.o.o.o
......|.|..
o.o.o-o.o.o
........|.|
o.o-o.o.o.o
..|...|....
o.o.o-o-o.o
|.|.....|..
o.o-o-o-o.o

5

2 3
o.o-o
|.|x|
o.o-o

0

The first example represents the grid in the middle of the picture.