CREC01 - Đếm hình chữ nhật trên bảng 0-1
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
//#include <conio.h>
int m,n,chay,
h[1002],s[1002];
long long KQ, soh[1002];
char a[1002];
int main()
{
//freopen("CREC01.in","r",stdin);
scanf("%d %d",&m,&n);
gets(a);
for(int i = 1;i<=m;i++)
{
gets(a);
for(int j = 1;j<=n;j++)
{
if(a[j-1]=='0') h[j]=0;
else h[j]++;
}
int chay = 0;s[0] = 0; soh [0] = 0; h[0] = -1;
for(int j = 1;j<=n;j++)
{
while(h[s[chay]]>=h[j]) chay--;
int flag = s[chay];
s[++chay] = j;
soh[j] = h[j]*(j-flag) + soh[flag];
KQ = KQ+soh[j];
}
}
printf("%lld",KQ);
//getch();
}