给出一个n×n的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色矩形的数量
第一行，一个整数n，表示矩形的大小。
接下来n行，每行n个字符，这些字符为“W”或“B”。其中“W”表示白格，“B”表示黑格。
一个正整数，为白色矩形数量
4 WWBW BBWB WBWW WBWB
15
对于30%的数据，n≤50；
对于100%的数据，n≤150；
矩形固定了左下角向右上方拓展着去找，即不会重复，也使思维变得简单了很多
每行开始时，预处理这一行每一列的高度，方便之后的统计， 然后确认往右拓展，能取的高度是拓展到的高度中的最小值，然后会发现以i, j为左下角宽度为k-j+1的矩形数量在数值上等于高度，累加后就是答案了
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200;
char map[N][N];
int n,ans,cnt[N];
int main () {
scanf("%d",&n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>map[i][j];
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++)
if(map[i][j]==‘B‘)
cnt[j]=0;
else
cnt[j]++;
for(int j=1; j<=n; j++) {
int flag=cnt[j];
for(int k=j; k<=n; k++) {
if(!cnt[k])
break;
flag=min(flag,cnt[k]);
ans+=flag;
}
}
}
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/mysh/p/11456616.html