首先可以用扫描法处理出一个height数组， 来保存从当前行开始， 每一个格子可以向上延伸的最大长度。
这种“延伸”的问题用扫描法， 因为往往这个时候可以利用前一次的结果来更新当前的值
然后这道题的关键就是是维护一个单调栈， 栈顶的元素就是当前状态所求的答案。
这个单调栈满足的性质是：c从小到大增加， h从小到大增加， h-c从小到大增加。c表示当前列， h表示height[c]
因为遍历的时候是从左到右的， 所以c就是一直增大的， 然后加入的时候有个while循环， 保证h是一直增大的，
最后加入的时候的if就是维护h-c是一直增大的。
这道题和防线那道题目很像， 都是维护一个双重有序的结构， 在加入新的元素的时候需要修改结构的值。只不过那道题是二分，这道题是单调栈。
#include<cstdio>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
char s[MAXN][MAXN];
int height[MAXN], ans[MAXN<<1], n, m, top;struct node
{int c, h;int val() { return h - c; }node(int c = 0, int h = 0) : c(c), h(h) {}
}stack[MAXN];int main()
{int T;scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);REP(i, 0, n) scanf("%s", s[i]);memset(height, 0, sizeof(height));memset(ans, 0, sizeof(ans));REP(i, 0, n){top = -1;REP(j, 0, m){if(s[i][j] == '#'){top = -1;height[j] = 0;continue;}height[j]++;node r(j, height[j]);if(top < 0) stack[++top] = r; else{while(top >= 0 && r.h <= stack[top].h) r.c = stack[top--].c;if(top < 0 || r.val() > stack[top].val()) stack[++top] = r;}ans[j+stack[top].val()+1]++;}}REP(i, 1, n + m + 1)if(ans[i])printf("%d x %d\n", ans[i], i * 2);}return 0;
}