本文共 1261 字，大约阅读时间需要 4 分钟。

原题链接：
分类：扫描法
备注：状态组织；单调栈

根据紫书上的描述，浅显易懂，一次就过了。首先存储好每个空地块最高高度。
关键点在于：①计算最长周长时，设当前列为$c_0$，左上角的列为$c$，高度为$h$，周长则为$2(c_0-c+1+h)$，因此周长由$c$和$h$来决定；②每一行从左往右遍历，单调栈来存储$h-c$，更小或者等于的左上角就不需要存储了，因为接下来的列如果最大高度更高，是不会影响已经存储的左上角，如果等于或者更低，显然$h-c$会更小，所以不需存储。

#include<bits/stdc++.h>using namespace std;int t,n,m,h[1005][1005],vis[4005],ans[4005];char g[1005][1005];struct Node{   	int col,h;}a[1005];int main(void){   	// freopen("in.txt","r",stdin);	scanf("%d",&t);	while(t--){   		scanf("%d%d",&n,&m);		for(int i=1;i<=n;i++)			scanf("%s",g[i]+1);		for(int j=1;j<=m;j++){   			for(int i=1;i<=n;i++){   				if(g[i][j]=='#')h[i][j]=0;				else h[i][j]=h[i-1][j]+1;			}		}		memset(vis,0,sizeof(vis));		int num=0;		for(int i=1;i<=n;i++){   			int tot=0;			for(int j=1;j<=m;j++){   				if(g[i][j]=='#'){   					tot=0; continue;				}				int col=j;				while(tot&&h[i][j]<a[tot].h){   					col=a[tot].col;						tot--;				}				if(!tot||h[i][j]-col>a[tot].h-a[tot].col){   					tot++; 					a[tot].h=h[i][j]; 					a[tot].col=col;				}				int len=(j-a[tot].col+1+a[tot].h)*2;				if(!vis[len])ans[num++]=len;				vis[len]++;			}		}		sort(ans,ans+num);		for(int i=0;i<num;i++)printf("%d x %d\n",vis[ans[i]],ans[i]);	}	return 0;}