问题 5317. -- 长方形-训练套题T3T3

5317: 长方形-训练套题T3T3

时间限制: 1 Sec  内存限制: 128 MB
献花: 3  解决: 0
[献花][花圈]

题目描述


3.长方形(rectangle.pas/c/cpp)


【问题描述】

Simo想从一张用过的纸中剪出一个长方形,规则如下:

(1)       这张纸的长度、宽度、分别为n,m。可以将这张纸看成是n*m个格子组成,在剪的时候,只能沿着格子边缘剪。

(2)       Simo以前在这张纸上画过画,剪出来的长方形不能含有画过的地方;

(3)       剪出来的长方形的大小没有限制。

请问有多少种不同的剪法。

【输入格式】

  第一行两个正整数,n,m,表示这张纸的长度和宽度。

  接下来有n行,每行m个字符,每个字符为“*”或“.”,分别表示画过和没画过。

【输出格式】

一个整数,表示方案数。

【输入样例】

6 4

....

.***

.*..

.***

...*

.***

【输出样例】

  38

【问题规模】

  对于10%的数据,满足1<=n,m<=10

对于30%的数据,满足1<=n,m<=50

对于60%的数据,满足1<=n,m<=200

对于100%的数据,满足1<=n,m<=1000

最后一个数据所有的字符都为“.”

输入

输出

提示


长方形



    【题目大意】



    在一个n·m的方格内,问有多少种不同的方法放一个长方形。某些指定的位置不能放。



    【解法一】



    最朴素的穷举法。先穷举长方形的四条边,时间为O(n^4),然后再判断是否可放,时



间为O(n^2)。总的时间复杂度为O(n^6)。预计得分为10



    【解法二】



    在解法一的基础上,改进判断能不能放的方法。先预处理出s数组,s[i][j]表示左



上方i*j大小的格子中有多少个字符为’*’。那么如果要判断从第i行到第j行,从第k



列到第1列的长方形中有没有字符’*’,就可以通过计算s[j][1]+s[i-1][k-1]-s[j][k-1]-s[i-1][1]而得到。如果这个值大于0,那么说明不可以放,如果等于0,那么可以放。



判断的时间被成功地降为O(1)。总的时间复杂度为O(n^4)。预计得分为30



    【解法三】



    在解法二的基础上,继续改进。先穷举长方形的上下两条边,然后用解法二的方法,判



断出在这两条边之间的每一列是否能放。然后从左到右扫一遍,对于某一段连续的能放的列,如果有k列,那么有k* (k+1)2种不同的放法。穷举的时间为O(n^2),统计的时间为



O(n),总时间为O(n^3)。预计得分为60



【解法四】



解法四比较复杂,要用到数据结构栈。这里就不详细介绍了。如果选手有兴趣,可以先



2 006年的国家集训队论文悠本数据结构在信息学竞赛中的应用》。本题由论文中的一



题改编而成,做法大同小异。此做法时间复杂度为O(n^2),预计得分100



    【出题人的意图】



    本题的原形是求面积最大的长方形。笔者稍作改变,变成求长方形的个数。解法一很



容易想到,但是效率不高,只给1
O
分。解法二是在解法一的基础上作了一个很经典的优



化,给3 0分。解法三没有完全穷举,只穷举了上下两条边,然后通过计算而得到答案,此做法得6 O分。解法四不易想到。本题的做法比较多,欢迎有想法的选手积极讨论,也希望选手能有更好的做法。

来源

[献花][花圈]