读书人

N*N的棋盘求棋盘上完全由白色正方形

发布时间: 2012-05-23 13:44:13 作者: rapoo

N*N的棋盘,求棋盘上完全由白色正方形构成的矩形的个数
百度上看到的问题,本来以为挺简单的,结果弄了好久才弄出来一个求能有多少矩形的,仔细看了下,不合题意,又想了好久也没想出来,最后采用比较所有矩形的坐标来从所有的矩形中删除被包含的,不知有没有好的办法。
有个N x N的棋盘,每一格都是同等大小的正方形,一些正方形被涂成了白色,剩下的则被涂成了黑色。现给定这样的一个棋盘,求出有多少个完全由白色正方形构成的矩形。
--------------------------------------------
输入样例:


2
.#..
4
..#.
##.#
.#..
.#.#
--------------------------------------------

输出样例:


2
3(我觉得这里应该输出是4才对啊,题目是3)
--------------------------------------------

[解决办法]

探讨
从大到小即从N×N、(N-1)×(N-1)、……、1×1大小的白色正方形穷举。较大正方形算过的话将其涂黑避免后面较小正方形重复计算?

读书人网 >C语言

热点推荐