当前位置：首页 > news >正文

P1191 矩形【洛谷算法习题】

news 2026/4/29 13:27:55

P1191 矩形

网页链接

P1191 矩形

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

4 WWBW BBWB WBWW WBWB

输出 #1

说明/提示

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

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

解题思路

本题核心是悬线法+区间枚举优化，高效统计矩阵中的全白矩形数量。遍历矩阵的每一行作为矩形的底边，维护数组h[j]表示第j列从当前行向上连续的白色格子数，遇到黑色格子则将值清零。针对每一行，枚举左边界j并向右扩展右边界k，遇到黑色格子立即剪枝中断，同时记录区间[j,k]内h的最小值，该最小值即为当前区间能构成的合法白色矩形数量，将其累加到总答案中。算法时间复杂度为O ( n 3 ) O(n^3)O(n3)，结合黑格剪枝优化，完美适配n ≤ 150 n≤150n≤150的数据规模。

总结

核心逻辑：悬线法记录列连续白格高度，枚举左右区间计算最小高度，累加得到白色矩形总数。
关键操作：维护连续白高数组、区间枚举剪枝、最小高度累加计数。
效率保障：O ( n 3 ) O(n^3)O(n3)复杂度适配题目约束，黑格剪枝大幅提升实际运行效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cin>>n;vector<int>h(n+2,0);intans=0;for(inti=1;i<=n;++i){for(intj=1;j<=n;++j){charc;cin>>c;if(c=='W')h[j]++;elseh[j]=0;}for(intj=1;j<=n;++j){intcur=h[j];for(intk=j;k<=n;++k){if(!h[k])break;cur=min(cur,h[k]);ans+=cur;}}}cout<<ans<<'\n';return0;}