C - Z塗り Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N \times N のマス目状に区切られており、すでにいくつかのマスは塗られています。i 行目 j 列目のマスをマス (i,j) と呼ぶことにします。高橋君は特殊なインク発射装置を用いて床を塗ろうとしています。この装置を使うと、以下のように床を塗ることができます。

  • 任意の整数 r, c を入力して装置のボタンを押すと、「i = r かつ j ≦ c」または「i = r+1 かつ j ≧ c」を満たすようなすべてのマス (i,j) を塗ることができる。

高橋君は、全てのマスをこの装置で塗ろうと思っています。このとき、装置を使う必要のある回数の最小値を求めてください。

入力

入力はイカの形式で標準入力から与えられる。

N
S_1
S_2
:
S_N
  • 1 行目には、マス目の 1 辺の個数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目からの N 行には、マス目の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、長さ N の文字列 S_i が与えられる。このうち j (1 ≦ j ≦ N) 文字目は、マス (i,j) の情報を以下のように表す。
    • . の場合：このマスがまだ塗られていないことを表す。
    • o の場合：このマスがすでに塗られていることを表す。

出力

装置を使う回数の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

7
...oooo
oo.....
ooooooo
ooooooo
.....oo
oooo...
ooooooo

出力例1

2

インク発射装置はこの入力のような形を綺麗に塗ることができます。

入力例2

4
.oo.
..oo
o..o
oo..

出力例2

3

入力例3

1
o

出力例3

0

はじめから全て塗られていることもあります。