/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
縦横それぞれ N マスからなる N \times N のグリッドがあります。上から i マス目、右から j マス目のマスのことを、マス (i, j) と呼びます。はじめ各マスは黒色か白色で塗られていて、色は入力で与えられる文字 S_{i, j} で表されます。マス (i, j) は S_{i, j} が # なら黒色、 . なら白色で塗られています。
あなたは、白色で塗られたマスを 1 つ選び黒色で塗る、という操作を繰り返すことで、マス目が以下の条件を満たすようにします。
- どの白色で塗られたマス (x, y) についても、マス (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) (ただし存在しないマスは除く) のうち、黒色で塗られたマスは 2 つ以下である。
最小で何回の操作でマス目が条件を満たすようにできるか、求めてください。
制約
- 1 \leq N \leq 2000
- S_{i, j} は
.か#
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1, 1} S_{1, 2} \cdots S_{1, N}
S_{2, 1} S_{2, 2} \cdots S_{2, N}
\vdots
S_{N, 1} S_{N, 2} \cdots S_{N, N}
出力
答えを 1 行に出力せよ。
入力例 1
3 ### #.# ###
出力例 1
1
マス (2, 2) は白色で塗られており、また上下左右のマスがいずれも黒色で塗られています。マス (2, 2) を黒色で塗り直すと、マス目が条件を満たすようになります。
入力例 2
3 ... #.# .#.
出力例 2
1
マス (2, 2) を黒色で塗り直すと、マス目が条件を満たすようになります。
入力例 3
5 ##### #.... #.### #...# #####
出力例 3
8
どの白く塗られたマスも黒く塗らないと、最終的に条件を満たすマス目にはなりません。
Problem Statement
There is an N \times N grid with N horizontal rows and N vertical columns. Let (i, j) denote the cell in the i-th row from the top and j-th column from the left. Initially, each cell is painted black or white; cell (i, j) is painted black if S_{i, j} is #, and white if S_{i, j} is ..
You will repeatedly choose one cell to paint black so that the grid satisfies the following condition:
- for any cell (x, y) painted white, at most two of cells (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) (except for non-existent ones) are painted black.
At least how many operations are required to meet the condition?
Constraints
- 1 \leq N \leq 2000
- S_{i, j} is
.or#.
Input
The input is given from Standard Input in the following format:
N
S_{1, 1} S_{1, 2} \cdots S_{1, N}
S_{2, 1} S_{2, 2} \cdots S_{2, N}
\vdots
S_{N, 1} S_{N, 2} \cdots S_{N, N}
Output
Print the answer in one line.
Sample Input 1
3 ### #.# ###
Sample Output 1
1
Cell (2, 2) is painted white, and all of the four adjacent cells are painted black. By repainting cell (2, 2) black, the grid satisfies the condition.
Sample Input 2
3 ... #.# .#.
Sample Output 2
1
By repainting cell (2, 2) black, the grid satisfies the condition.
Sample Input 3
5 ##### #.... #.### #...# #####
Sample Output 3
8
The grid satisfies the condition only when all the white cells are repainted black.