Score : 1300 points
There is a square-shaped grid with N vertical rows and N horizontal columns. We will denote the square at the i-th row from the top and the j-th column from the left as (i,\ j).
Initially, each square is either white or black.
The initial color of the grid is given to you as characters a_{ij}, arranged in a square shape.
If the square (i,\ j) is white, a_{ij} is .
. If it is black, a_{ij} is #
.
You are developing a robot that repaints the grid. It can repeatedly perform the following operation:
Your objective is to turn all the squares black. Determine whether it is possible, and find the minimum necessary number of operations to achieve it if the answer is positive.
.
or #
.The input is given from Standard Input in the following format:
N a_{11}...a_{1N} : a_{N1}...a_{NN}
If it is possible to turn all the squares black, print the minimum necessary number of operations to achieve the objective.
If it is impossible, print -1
instead.
2 #. .#
3
For example, perform the operation as follows:
The transition of the colors of the squares is shown in the figure below:
2 .. ..
-1
2 ## ##
0
3 .#. ### .#.
2
3 ... .#. ...
5