紫书上分析了很多很多，超详细，=￣ω￣=
每扫描一行可以计算一个height数组，表示从这块空地向上延伸多少块空地，而且这个数组可以逐行递推。
首先对于每一行来说维护一个单调栈，栈里放的是矩形的左上角，而且横坐标c和高度h也都是递增的，另外对于扫描到的同一个右下角，矩形面积的大小只与左上角的横坐标c和高度h的差值h-c有关，所以栈里面的h-c也都是递增的。
另外，计算出来当前的height[j]的时候有可能会“削减”栈中的矩形。
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
char s[maxn][maxn]; int height[maxn], ans[maxn << ]; struct Rect
{
int c, h;
Rect(int c = , int h = ):c(c), h(h) {}
}rect[maxn]; int n, m; int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++) scanf("%s", s[i]); memset(height, , sizeof(height));
memset(ans, , sizeof(ans)); for(int i = ; i < n; i++)
{
int top = -;
for(int j = ; j < m; j++)
{
if(s[i][j] == '#')
{
top = -;
height[j] = ;
}
else
{
height[j]++;
Rect r(j, height[j]);
if(top < ) rect[++top] = r; //空栈直接入栈
else
{
while(top >= && rect[top].h >= r.h) r.c = rect[top--].c; //栈中的h应小于height[j]
if(top < || r.h - r.c > rect[top].h - rect[top].c) rect[++top] = r;
}
r = rect[top];
ans[r.h + j - r.c + ]++;
}
}
}
for(int i = ; i <= m + n; i++) if(ans[i]) printf("%d x %d\n", ans[i], i * );
} return ;
}
代码君