006 - 回れ雛月花 -Hard

問題

あっ！！雛ちゃんだ！！可愛い！！！

雛ちゃんは、今日も厄集めをしようとしていた。

しかし、例によって厄集めをする土地は岩のせいで迷路のようになっている。

雛ちゃんはこの岩のお陰でいつも迷子になりかけているのだ。

刹那、雛ちゃんに電流走る！！

「岩が邪魔なら壊してしまえばいいじゃない！！」

というわけで雛ちゃんは弾幕で岩を破壊することにした！！いぇい！！

さて、厄集めをする土地が縦横均等に分けられた土地であることは周知の上であろう。

雛ちゃんの弾幕は、縦もしくは横一列に岩を破壊することが出来る。

もっとメタく言えば、ある縦座標もしくは横座標にある岩を破壊できるということだ。

さて、雛ちゃんだって疲れるので、あまり弾幕を使いたくない。

それを見かねたあなたは、最低何回の弾幕で土地上の全ての岩を破壊できるかを

雛ちゃんに教えるプログラムを作成しようと思った。

がんばれ。

入力形式

一行目に、雛ちゃんが厄集めをする土地の縦と横のマスの数 N が与えられる。

二行目から N行にかけて、土地の状態 p_i,j が与えられる。

"#" は岩であり、今回のターゲットである。

"." は更地であり、移動が出来る為、ターゲットではない。

N
p1,1 p1,2 ... p1,N
p2,1 p2,2 ... p2,N
..
pN,1 pN,2 ... pN,N

出力形式

土地上の全ての岩を破壊するにあたり最小の弾幕を放つ回数を一行に出力せよ。

制約

• 1 ≦ N ≦ 500

小課題

• 小課題一：　N ≦ 　10
• 小課題二：　N ≦ 　50
• 小課題三：　N ≦　 400
• 小課題四：　追加の制限は無い。

入出力例

入力例壱

4
.#.#
..#.
..#.
....

出力例壱

2

この場合弾幕を放つ地点は次の二つである。

　・H=1

　・W=3

入力例弐

5
.....
#...#
#.#..
.#...
.....

出力例弐

3