問題一覧 > 通常問題

No.640 76 Trombones

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 42
作問者 : square1001 / テスター : WA_TLE
お気に入りにしたユーザー ProblemId : 1932 / 自分の提出
問題文最終更新日: 2026-06-25 06:36:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 181 (順位表) の他の問題:

Problem Statement

There is an instrument storeroom represented by an $N \times N$ grid, into which you put $X$ trombones, each represented by a $1 \times (N - 1)$ rectangle.
Trombones may be rotated, but they must fit the grid, that is, all sides of each trombone must lie along the grid lines.
Also, trombones cannot overlap one another, and no cell of the storeroom containing an obstacle may be covered by any part of a trombone.
Find the maximum $X$ such that all the trombones can be stored.

Input

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

If $S_{i, j}$ is '#', an obstacle is placed on the cell that is $i$-th from the top and $j$-th from the left of the storeroom; if it is '.', no obstacle is placed there.

Output

Output the answer on one line, followed by a newline at the end.

Constraints

  • $3 \le N \le 75$

    • Sample

    Sample 1
    Input
    3
#..
...
..#
    Output
    3

    If the cells of the first trombone are denoted by '1', those of the second trombone by '2', and those of the third trombone by '3', they can be placed as follows.

    #11
23.
23#
    Also, since it is impossible to place 4 or more, the answer is 3.

    Sample 2
    Input
    5
#.#.#
.....
#.#.#
#.#.#
.....
    Output
    3

    By placing them as follows, 3 trombones can be stored. 

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

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