ICPC North America Qualifier 2016, Problem E

Alice and Bob are playing Dots and Boxes. The game is played on an $N\times N$ square lattice of dots, and they alternate drawing a line segment between horizontally or vertically adjacent dots that haven't been connected before. Every time a unit square is formed by four line segments, the player who put down the last segment scores one point for that square. The game ends when the square lattice has been completely filled with line segments, and whoever scored the most points wins.

Alice and Bob aren't really in a competitive mood today, so they've just been playing for fun. Hence they aren't following any specific game strategy, and, in particular, even if it's possible to make a move that scores a point or is clearly superior in some way, they won't necessarily make that move. But now they've been playing for a while and neither of them has scored a single point. If neither of them scores a point pretty soon, they may get bored. Given the current state of the game, how many moves could be made, in the worst case, before either Alice or Bob is guaranteed to have scored a point?

Input Specification

Input starts with a line containing an integer $N$ $(2\le N\le 80)$, the size of the square lattice. Then follows an ASCII representation of the current state of the game, $2N-1$ rows high and $2N-1$ columns wide, listed in row-major order. There are cells of four types $(1\le i,j\le N)$:

• Cell $(2i-1,2j-1)$ is *, representing dot $(i,j)$.
• Cell $(2i,2j)$ is ., representing empty space.
• Cell $(2i,2j-1)$ is | if dots $(i,j)$ and $(i+1,j)$ have been connected by a line segment, and . otherwise.
• Cell $(2i-1,2j)$ is - if dots $(i,j)$ and $(i,j+1)$ have been connected by a line segment, and . otherwise.

It is guaranteed that no player has scored a point, meaning that no unit squares have been formed.

Output Specification

Output the number of moves that can be made, in the worst case, before either Alice or Bob is guaranteed to have scored a point.

Sample Input 1

3
*-*.*
|.|.|
*.*-*
|...|
*.*.*

Sample Output 1

3

Sample Input 2

2
*.*
...
*.*

Sample Output 2

4

Sample Input 3

4
*-*-*.*
|...|..
*-*-*-*
|.....|
*.*.*-*
|.....|
*-*-*-*

Sample Output 3

5