Rectangle Painting 1

题意翻译

给 $n\times n$ 矩阵只含 ``.``或``#``，请用价值和最少的一堆长方形覆盖所有的 ``#``，一个长方形的价值是长与宽的最大值 第一行一个整数 $n(1\le n\le 50)$ 接下来 $n$ 行每行 $n$ 个字符

题目描述

There is a square grid of size $ n \times n $ . Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $ \max(h, w) $ to color a rectangle of size $ h \times w $ . You are to make all cells white for minimum total cost.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the size of the square grid. Each of the next $ n $ lines contains a string of length $ n $ , consisting of characters '.' and '\#'. The $ j $ -th character of the $ i $ -th line is '\#' if the cell with coordinates $ (i, j) $ is black, otherwise it is white.

输出格式

Print a single integer — the minimum total cost to paint all cells in white.

输入输出样例

输入样例 #1

3
###
#.#
###

输出样例 #1

3

输入样例 #2

3
...
...
...

输出样例 #2

0

输入样例 #3

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

输出样例 #3

2

输入样例 #4

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

输出样例 #4

5

说明

The examples and some of optimal solutions are shown on the pictures below.