← 返回题目

题库练习 Rectangle Painting 1

← 上一题下一题 →

A12855 | $Rectangle Painting 1$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #2

3
...
...
...

输出 #2

输入 #3

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

输出 #3

输入 #4

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

输出 #4

C++ 编辑器

输入

输出