3603: 长方形-训练套题T3T3
Description
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
最后一个数据所有的字符都为“.”
HINT
长方形
【题目大意】
在一个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分。解法四不易想到。本题的做法比较多，欢迎有想法的选手积极讨论，也希望选手能有更好的做法。