uva12265 贩卖土地单调栈

输入一个n*m的矩阵，每个格子可能是空地，也可能是沼泽。对于每个空地格子，求出以它为右下角的空矩形的最大周长，然后统计每个周长出现了多少次。

输入包含多组测试数据，第一行输入一个正整数N，表示输入样例组数(N<=10)
每组测试样例第一行为正整数n和m(1<=n,m<=1000)
以下n行，每行包含m个字符，用'#'表示沼泽，'.'表示土地

输出数据包含多行，用"a x b"来表示周长为b的矩形出现了a次，按照矩形周长从小到大排序

1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.

6 x 4
5 x 6
5 x 8
3 x 10
1 x 12

显而易见，我们要维护一个单调上升的关于每列高度的栈，然而此题仅仅维护高度明显不够，对于一个矩形的边长，我们可有宽度和高度得知。

对于单调栈的每一个元素，我们维护宽度和高度两个元素，为此列的高度和最左端的位置。对于一个矩形，我们有周长=（h+j-c+1）*2，由于对于每一列，j一定，所以h+c最大就是周长最大，因此我们的单调栈不仅要维护长度递增，还要在插入时有所选择，维护h+c的单调递增序列。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 struct data

 {

     int x,y;

 }sta[];

 int n,m;

 char a[][];

 int h[];

 int ans[];

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         memset(ans,,sizeof(ans));

         memset(h,,sizeof(h));

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)scanf("%s",a[i]+);

         for(int i=;i<=n;i++)

         {

             int head=;

             for(int j=;j<=m;j++)

             {

                 int he=h[j],k=j;

                 if(a[i][j]=='#'){h[j]=;head=;}

                 else

                 {

                     he++;h[j]++;

                     while(head>=&&sta[head].x>=h[j]){k=sta[head].y;head--;}

                     if(!head||he-k>sta[head].x-sta[head].y){sta[++head]=(data){he,k};}

                     ans[sta[head].x+j-sta[head].y+]++;

                 }

             }

         }

         for(int i=;i<=m+n;i++) if(ans[i]) printf("%d x %d\n",ans[i],i*);

     }

 }

巴特西

uva12265 贩卖土地单调栈

最新文章

热门文章

巴特西

uva12265 贩卖土地 单调栈

最新文章

热门文章

uva12265 贩卖土地单调栈