Dots and Boxes

Time limit2sMemory limit512 MB

Summary

Given a Dots and Boxes position with no completed square, find the longest sequence of moves that still avoids closing any square, then print that length plus one.

Level: Hard8 of 10
Topics: Graph, Dynamic programming, Combinatorics, Implementation
Solved: No attempts yet

Problem

Alice and Bob play Dots and Boxes on a square lattice of $N \times N$ dots. They move alternately. One move draws a segment between two dots that are neighbours horizontally or vertically and are not connected yet. When four segments close a unit square, the player who drew the last of those four segments scores one point for that square. The game ends once every possible segment has been drawn, and the player with more points wins.

Today the two are not in a competitive mood, so neither follows a strategy. Even when a move would score a point, a player can leave it and play somewhere else. They have been playing for a while and neither has scored yet. If nobody scores soon, they will get bored.

You are given the current position. Let $k$ be the largest number of moves that can still be played without closing a single square. After those $k$ moves every remaining segment closes a square, so the move numbered $k + 1$ scores a point. Print $k + 1$ , the number of moves that can be made in the worst case before Alice or Bob has certainly scored.

Input

The first line contains one integer $N$ ( $2 \le N \le 80$ ), the number of dots along one side of the lattice.

The next $2N - 1$ lines contain $2N - 1$ characters each and describe the current position in row major order. Rows and columns are numbered from $1$ .

Cell $(2i - 1, 2j - 1)$ is * and marks dot $(i, j)$ , for $1 \le i \le N$ and $1 \le j \le N$ .
Cell $(2i - 1, 2j)$ is - when dots $(i, j)$ and $(i, j + 1)$ are connected by a segment, and . otherwise, for $1 \le i \le N$ and $1 \le j \le N - 1$ .
Cell $(2i, 2j - 1)$ is | when dots $(i, j)$ and $(i + 1, j)$ are connected by a segment, and . otherwise, for $1 \le i \le N - 1$ and $1 \le j \le N$ .
Cell $(2i, 2j)$ is ., for $1 \le i \le N - 1$ and $1 \le j \le N - 1$ .

No unit square is closed in the given position, so neither player has scored.

Output

Print one integer, the number of moves that can be made in the worst case before Alice or Bob has certainly scored a point.

Examples3

Example 1
Input
```
3
*-*.*
|.|.|
*.*-*
|...|
*.*.*
```
Expected output
```
3
```
Example 2
Input
```
2
*.*
...
*.*
```
Expected output
```
4
```

Example 3

Input

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

Expected output