No.640 76本のトロンボーン

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : square1001square1001 / テスター : WA_TLEWA_TLE
1 ProblemId : 1932 / 出題時の順位表

問題文

$N \times N$ のマス目で表される楽器庫があり、$1 \times (N - 1)$ の長方形で表されるトロンボーンを $X$ 個入れる。
トロンボーンは回転させることができるが、マス目に入ってなければならない、すなわちトロンボーンの辺がすべてマス目の区切りの部分に入っていなければならない。
また、トロンボーンは重なって置くことができず、楽器庫の障害物が置かれているマスがトロンボーンの一部分に入ってはいけません。
そのとき、すべてのトロンボーンが収納できるような最大の $X$ を求めなさい。

入力

$N$
$S_{1, 1} S_{1, 2} \cdots S_{1, N}$
$S_{2, 1} S_{2, 2} \cdots S_{2, N}$
:   :      :
$S_{N, 1} S_{N, 2} \cdots S_{N, N}$

$S_{i, j}$ が '#' であれば、楽器庫の上から $i$ 番目、左から $j$ 番目のマスに障害物がおかれており、'.' の場合障害物がおかれていないということを示します。

出力

答えを1行に出力しなさい。また、最後に改行してください。

制約

  • $3 \le N \le 75$
  • サンプル

    サンプル1
    入力
    3
    #..
    ...
    ..#
    
    出力
    3
    

    1個目のトロンボーンのマスを '1'、2個目のトロンボーンのマスを '2'、3個目のトロンボーンのマスを '3' で表すと、次のように置くことができます。

    #11
    23.
    23#
    
    また、4個以上置くことができないので、答えは 3 となります。

    サンプル2
    入力
    5
    #.#.#
    .....
    #.#.#
    #.#.#
    .....
    
    出力
    3
    

    次のように置くと、3つのトロンボーンを収納することができます。

    #1#2#
    .1.2.
    #1#2#
    #1#2#
    3333.
    

    提出ページヘ
    下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

    言語
    問題によって提出できない言語があります。参考
    ソースコード
    ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
    テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。