問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : square1001square1001 / テスター : WA_TLEWA_TLE
1 ProblemId : 1932 / 出題時の順位表
問題文最終更新日: 2018-03-06 15:33:58

問題文

$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.
    

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。