【滑动窗口二维前缀和】P10719 [GESP202406 五级] 黑白格|普及

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。## 输入格式第一行包含三个正整数 $n,m,k$，含义如题面所示。之后 $n$ 行，每行⼀个长度为 $m$ 的 $\texttt{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\texttt{0}$，则对应格子为白色，否则为黑色。##

闻缺陷则喜何志丹

1013人浏览 · 2025-02-23 07:00:00

闻缺陷则喜何志丹 · 2025-02-23 07:00:00 发布

本文涉及的基础知识点

C++算法：滑动窗口及双指针总结
 C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
 本博文代码打包下载

[GESP202406 五级] 黑白格

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。

输入格式

第一行包含三个正整数 $n, m, k$ ，含义如题面所示。

之后 $n$ 行，每行⼀个长度为 $m$ 的 $\texttt{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\texttt{0}$ ，则对应格子为白色，否则为黑色。

输出格式

输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 $0$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

对于样例 $1$ ，假设 $(i, j)$ 代表第 $i$ 行第 $j$ 列，至少包含 $5$ 个黑色格子的最小子矩形的四个顶点为 $(2, 4)$ ， $(2, 5)$ ， $(4, 4)$ ， $(4, 5)$ ，共包含 $6$ 个格子。

数据范围

对于全部数据，保证有 $1\le n,m\le 100$ ， $1\le k\le n\times m$ 。

子任务编号	得分	$n, m$
$1$	$20$	$\le 10$
$2$	$40$	$n = 1$ ， $1\le m\le 100$
$3$	$40$	$\le 100$

Update on 2024/7/9：添加了若干组 hack 数据，感谢 @cff_0102 的贡献。

滑动窗口+ 前缀和

暴力做法是枚举起始位置和行列，时间复杂度是：O(nmnm)，可能超时。
mat记录网格信息，mat[r][c]表示第r行c列是否是黑色格子。
枚举网格，第一层高度为height，第二层其实行行号r。
第三层枚举其实列号c，通过滑动窗口枚举结束列号c2。行在左闭右开空间[r,r+height),列在左闭半开的区间[c,c2)的黑色单格数大于等于k。c增加，c2增加或不变，绝对不会变小。
最小：height*(c2-c)就是答案。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret(n);
	for(int i=0;i<n;i++) {
		scanf(pFormat, &ret[i]);	
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {
	cin >> pr.first >> pr.second;
}

template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist(_Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd(_Pr pr)
	{
		INDEX_TYPE leftInclude = m_iMin;
		INDEX_TYPE right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};

template<class T = int>
class CPreSum2 {
public:
	template<class _Pr>
	CPreSum2(int rowCnt, int colCount, _Pr pr) :m_iRowCnt(rowCnt), m_iColCnt(colCount) {
		m_vSum.assign(rowCnt + 1, vector<int>(colCount + 1));
		for (int r = 0; r < rowCnt; r++) {
			for (int c = 0; c < colCount; c++) {
				m_vSum[r + 1][c + 1] = m_vSum[r][c + 1] + m_vSum[r + 1][c] - m_vSum[r][c] + pr(r, c);
			}
		}
	}
	T Get(int left, int top, int right, int bottom)const {
		return m_vSum[bottom + 1][right + 1] - m_vSum[top][right + 1] - m_vSum[bottom + 1][left] + m_vSum[top][left];
	}
	T GetTopLeft(int bottom, int right) { return m_vSum[bottom + 1][right + 1]; }
	T GetBottomRight(int top, int left) { return Get(left, top, m_iColCnt - 1, m_iRowCnt - 1); }
	vector<vector<T>> m_vSum;
	const int m_iRowCnt, m_iColCnt;
};
class Solution {
public:
	int Ans(vector<string>& mat, const int K) {
		const int R = mat.size(), C = mat[0].size();
		CPreSum2<int> ps(R, C, [&](int r, int c) {return mat[r][c] - '0'; });
		int ans = INT_MAX / 2;
		for (int height = 1; height <= R; height++) {
			for (int r = 0; r + height <= R; r++) {
				for (int c = 0, c2 = 1; c < C; c++) {
					while ((c2 < C) && (ps.Get(c, r, c2 - 1, r + height - 1) < K)) {
						c2++;
					}
					if (ps.Get(c, r, c2 - 1, r + height - 1) >= K) {
						ans = min(ans, height * (c2 - c));
					}
				}
			}
		}
		return (INT_MAX / 2 == ans) ? 0 : ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int R,C,K;
	cin >> R >> C >> K;
	vector<string> mat(R);
	for (int r = 0; r < R; r++) {
		cin >> mat[r];
	}
	auto res = Solution().Ans(mat,K);
#ifdef _DEBUG			
		//Out(mat, "mat=");
		//Out(b, ",b=");	
		//printf("K=%d", K);
#endif		
	cout << res << std::endl;		
	return 0;
}

单元测试

vector<string> mat;
		int K;
		TEST_METHOD(TestMethod11)
		{
			mat = { "00000","01111","00011","00011" },K = 5	;
			auto res = Solution().Ans(mat,K);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			mat = { "00000","01111","00011","00011" }, K = 50;
			auto res = Solution().Ans(mat, K);
			AssertEx(0, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功