/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N \times N のグリッドがあり、いくつかのマスにはブロックが置いてあります。
グリッドの情報は N 個の文字列 S_1,S_2,\dots,S_N によって以下の形式で与えられます。
- S_i の j 文字目が
#のとき、グリッドの上から i マス目、左から j マス目にブロックがある。 - S_i の j 文字目が
.のとき、グリッドの上から i マス目、左から j マス目にブロックがない。
高橋くんは、以下の操作を 0 回以上好きなだけ行うことができます。
- まず、 1 以上 N 以下の整数 D と、グリッド内の D \times D の部分正方形を選ぶ。
- その後、体力 D を消費して部分正方形内のブロックをすべて破壊する。
高橋くんがすべてのブロックを破壊するのに必要な体力の最小値を求めてください。
制約
- N は整数
- 1 \le N \le 50
- S_i は
#と.のみからなる - |S_i|=N
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
5 ##... .##.. #.#.. ..... ....#
出力例 1
4
以下の部分正方形を選ぶことで、消費する体力を 4 にすることができ、これが最適です。
- 上から 1 マス目、左から 1 マス目を左上とした、 3 \times 3 の部分正方形
- 上から 5 マス目、左から 5 マス目を左上とした、 1 \times 1 の部分正方形
入力例 2
3 ... ... ...
出力例 2
0
グリッドにブロックが 1 つもない場合もあります。
入力例 3
21 ..................... ..................... ...#.#............... ....#.............#.. ...#.#...........#.#. ..................#.. ..................... ..................... ..................... ..........#.....#.... ......#..###......... ........#####..#..... .......#######....... .....#..#####........ .......#######....... ......#########...... .......#######..#.... ......#########...... ..#..###########..... .........###......... .........###.........
出力例 3
19
Score : 600 points
Problem Statement
There is a N \times N grid, with blocks on some squares.
The grid is described by N strings S_1,S_2,\dots,S_N, as follows.
- If the j-th character of S_i is
#, there is a block on the square at the i-th row from the top and j-th column from the left. - If the j-th character of S_i is
., there is not a block on the square at the i-th row from the top and j-th column from the left.
Takahashi can do the operation below zero or more times.
- First, choose an integer D between 1 and N (inclusive), and a D \times D subsquare within the grid.
- Then, consume D stamina points to destroy all blocks within the subsquare.
Find the minimum number of stamina points needed to destroy all the blocks.
Constraints
- N is an integer.
- 1 \le N \le 50
- S_i consists of
#and.. - |S_i|=N
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
5 ##... .##.. #.#.. ..... ....#
Sample Output 1
4
By choosing the subsquares below, Takahashi will consume 4 stamina points, which is optimal.
- The 3 \times 3 subsquare whose top-left square is at the 1-st row from the top and 1-st column from the left.
- The 1 \times 1 subsquare whose top-left square is at the 5-th row from the top and 5-th column from the left.
Sample Input 2
3 ... ... ...
Sample Output 2
0
There may be no block on the grid.
Sample Input 3
21 ..................... ..................... ...#.#............... ....#.............#.. ...#.#...........#.#. ..................#.. ..................... ..................... ..................... ..........#.....#.... ......#..###......... ........#####..#..... .......#######....... .....#..#####........ .......#######....... ......#########...... .......#######..#.... ......#########...... ..#..###########..... .........###......... .........###.........
Sample Output 3
19