Luogu P1191 矩形【题解】

题目描述

给出一个n×n的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色矩形的数量。

输入输出格式

输入格式：

第一行，一个整数n，表示矩形的大小。

接下来n行，每行n个字符，这些字符为“W”或“B”。其中“W”表示白格，“B”表示黑格。

输出格式：

一个正整数，为白色矩形数量

输入输出样例

输入样例#1：

4
WWBW
BBWB
WBWW
WBWB

输出样例#1： 复制

15

说明

对于30%的数据，n≤50；

对于100%的数据，n≤150；

洛谷上这个题其实是可以n4过的，直接枚举就行，这里讲一下n3做法。

首先处理一下每行的高度，就是h数组，然后循环判断连续个数，累加即可。

//参考_Atyou大神代码
#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch==\'-\',ch=getchar();
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
char c[157][157];
int n,h[157],ans;
int main() {
	int n=read();
    for(int i=1;i<=n;i++)scanf(\"%s\",c[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)//扫一遍
            if(c[i][j]!=\'B\')h[j]++;//判断每行连续的白色个数
            else h[j]=0;//因为只统计白色高度，所以如果遇到黑色就清零
        for(int j=1;j<=n;++j){
        	int high=h[j];  
            for(int k=j;k<=n;++k){
                if(!h[k])break;
                high=min(high,h[k]);//连续个数取min
                ans+=high;//矩形个数=连续个数
            }
        }
    }
    printf(\"%d\\n\",ans);
    return 0;
}

又：考试考到这个题的强化版，n≤2000，留坑待填。