CREC01 - Đếm hình chữ nhật trên bảng 0-1

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<stack>
#define MAX   1010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
char a[MAX][MAX];
int h[MAX][MAX];
int l[MAX];
int c[MAX][MAX];
int m,n;
stack<int> st;
void init(void) {
	scanf("%d",&m);
	scanf("%d",&n);
	FOR(i,1,m) {
		scanf("%s",a[i]+1);
		FOR(j,1,n) {
			if (a[i][j]=='1') h[i][j]=h[i-1][j]+1;
			else h[i][j]=0;
		}
	}
}
void count(void) {
	FOR(i,1,m) {
		while (!st.empty()) st.pop();
		l[1]=1;
		c[i][1]=h[i][1];			
		FOR(j,2,n) {
			if (h[i][j]>h[i][j-1]) {
				l[j]=j;
				st.push(j-1);
			}
			else {
				while (!st.empty() && h[i][st.top()]>=h[i][j]) st.pop();
				if (st.empty()) l[j]=1;
				else l[j]=st.top()+1;
			}
			c[i][j]=c[i][l[j]-1]+h[i][j]*(j-l[j]+1);
		}
	}
	long long res=0;
	FOR(i,1,m) FOR(j,1,n) res+=c[i][j];
	printf("%lld",res);
}
int main(void) {
	init();
	count();
	return 0;
}

Download