Problem 1012
Description
You are given a chessboard made up of N squares by M squares. Some of the squares are colored black, and the others are colored white. Please
write a program to calculate the number of rectangles which are completely made up of white squares.
Input
There are multiple test cases. Each test case begins with two integer N,M (1 <= N , M<= 2000), the board size. The following N lines, each with M
characters, have only two valid character values:
b - representing a black square;
w - representing a white square.
Process to the end of file.
Output
For each test case in the input, output the number of white rectangles a line.
Sample Input
2 3
bbb
www
2 2
bw
wb
Sample Output
6
2
Hint
Source
The 4th Wuhan University Programming Contest(Preliminary Round)
坑爹的是把數組賦初值改成memset就tle了，我去，我說棧優化O（n）復雜度的算法怎麼都不可能tle啊！這oj真沒良心。。
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
#define pb push_back
#define MM(name,what) memset(name,what,sizeof(name))
typedef long long i64;
const int maxn = 2010;
const int inf = 0x3f3f3f3f;
struct zz
{
int x;
int re;
}zx;
int h[maxn][maxn];
char c[maxn][maxn];
int n,m;
vector<zz>s;
i64 gao(int id)
{
i64 ans = 0;
int temp = 0;
s.clear();
zx.x = -1;
zx.re = 0;
s.pb(zx);
for(int i=1;i<=n;i++)
{
zx.x = h[i][id];
zx.re = 1;
while(zx.x < s.back().x)
{
temp -= s.back().x*s.back().re;
zx.re += s.back().re;
s.pop_back();
}
temp+=zx.x*zx.re;
s.pb(zx);
ans+=temp;
}
return ans;
}
i64 start()
{
i64 ans=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
h[i][j]=0;
// MM(h,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(c[i][j]=='w') h[i][j]=h[i][j-1]+1;
for(int j=1;j<=m;j++)
{
ans+=gao(j);
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c[i][j] = getchar();
}
getchar();
}
// cout<<start()<<endl;
printf("%I64d\n",start());
}
return 0;
}
