/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 行 N 列のグリッドがあります。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは白または黒に塗られています。グリッドの情報は N 個の文字列 S_1, S_2, \ldots, S_N によって与えられ、S_i の j 文字目が . のときマス (i, j) は白く塗られており、S_i の j 文字目が # のときマス (i, j) は黒く塗られています。
あなたは、いくつかのマスの色を塗り替えて以下の条件をともに満たすようにします。
- すべての行に対して以下の条件が成り立つ。
- 0 \leq k \leq N を満たす整数 k が存在して、その行の左から k 個のマスは白く塗られており、その他のマスは黒く塗られている。
- すべての列に対して以下の条件が成り立つ。
- 0 \leq k \leq N を満たす整数 k が存在して、その列の上から k 個のマスは白く塗られており、その他のマスは黒く塗られている。
条件を満たすために塗り替える必要のあるマスの数として考えられる最小値を求めてください。
制約
- 1 \leq N \leq 5000
- N は整数
- S_i は
.,#からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 ..# #.# .#.
出力例 1
2
マス (2, 1) の色を白に、マス (3, 3) の色を黒に塗り替えることで条件を満たすことができます。
入力例 2
5 ..#.# #..## ###.# .###. #....
出力例 2
9
Score : 500 points
Problem Statement
There is a grid with N rows and N columns. The square at the i-th row from the top and j-th column from the left is denoted as square (i, j).
Each square in the grid is painted white or black. The information of the grid is given by N strings S_1, S_2, \ldots, S_N. If the j-th character of S_i is ., square (i, j) is painted white; if the j-th character of S_i is #, square (i, j) is painted black.
You will repaint some squares so that both of the following conditions are satisfied:
- For every row, the following condition holds:
- There exists an integer k satisfying 0 \leq k \leq N such that the leftmost k squares of that row are painted white and the other squares are painted black.
- For every column, the following condition holds:
- There exists an integer k satisfying 0 \leq k \leq N such that the topmost k squares of that column are painted white and the other squares are painted black.
Find the minimum number of squares that need to be repainted to satisfy the conditions.
Constraints
- 1 \leq N \leq 5000
- N is an integer.
- S_i is a string of length N consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
3 ..# #.# .#.
Sample Output 1
2
You can satisfy the conditions by repainting square (2, 1) white and square (3, 3) black.
Sample Input 2
5 ..#.# #..## ###.# .###. #....
Sample Output 2
9