P83026

刷方块

难度 6 级 初三 动态规划入门 区间 二维
讨论 统计 19通过 46提交 41.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一个n×n大小的方格图,某些方格初始是黑色,其余为白色。一次操作,可以选定一个h×w的矩形,把其中所有方格涂成白色,代价是max(h, w)。要求用最小的代价把所有方格变成白色。

输入

第1行是整数n,表示方格的大小。后面有n行,每行长度为n的串,包含符号’.‘和’#’,’.‘表示白色,’#'表示黑色。第i行的第j个字符是(i, j)。n ≤ 50。

输出

打印一个整数,表示把所有方格涂成白色的最小代价。

样例

样例 1
输入
5
# . . . #
. # . # .
. . . . .
. # . . .
# . . . .
输出
5

提示

注意,输入样例中,为显示方便,#和.之间有空格。在测试数据中,#与.之间是没有空格的。

对于100%的数据,n<=50。

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交