【图论并集查找】P3671 [USACO17OPEN] Where‘s Bessie? S|普及+

本文涉及知道点

C++图论
C++并集查找预计2025年5月29号 7:00发布

P3671 [USACO17OPEN] Where’s Bessie? S

题目描述

Farmer John 一直以精通技术而闻名，他正在测试他的新型无人机搭载的奶牛定位相机。这款相机据说可以拍摄他的田地并自动确定奶牛的位置。不幸的是，相机的算法并不擅长寻找奶牛，因此 Farmer John 需要你的帮助来开发一个更好的算法。

相机拍摄的农场俯视图由一个 $\times N$ 的字符网格描述，每个字符在 $\ldots Z$ 范围内，代表 26 种可能的颜色之一。Farmer John 认为，定义潜在奶牛位置（PCL）的最佳方式如下：一个 PCL 是一个矩形子网格（可能是整个图像），其边与图像的边平行，并且不包含在任何其他 PCL 中（因此 PCL 的较小子集不能也是 PCL）。此外，PCL 必须满足以下属性：仅关注矩形内的内容并忽略图像的其余部分，必须恰好存在两种颜色，其中一种颜色形成一个连续区域，另一种颜色形成两个或更多连续区域。

例如，一个矩形的内容如下：

AAAAA  
ABABA  
AAABB

这将构成一个 PCL，因为 A 形成一个连续区域，而 B 形成多个连续区域。解释为一只颜色为 A 的奶牛带有颜色为 B 的斑点。

一个区域是“连续的”，如果可以通过向上、向下、向左或向右移动，从一个区域中的单元格反复移动到另一个区域中的单元格来遍历整个区域。

给定 Farmer John 的相机返回的图像，请计算 PCL 的数量。

输入格式

输入的第一行包含 $N$ ，表示网格的大小（ $\leq N \leq 20$ ）。

接下来的 $N$ 行描述图像，每行包含 $N$ 个字符。

输出格式

输出图像中 PCL 的数量。

输入输出样例 #1

输入 #1

4
ABBC
BBBC
AABB
ABBC

输出 #1

说明/提示

在这个例子中，两个 PCL 分别是内容如下的矩形：

ABB  
BBB  
AAB  
ABB

和

BC  
BC  
BB  
BC

图论之并集查找(错误）

错误论点：如果(x1,y1)和(x2,y2)在某个矩形连通（不连通），则在整个图像连通（不连通）。反例如下图：黑线在绿色矩形不连通，整个图像连通。故不能预处理连通区域。
在这里插入图片描述

寻找符合两天条件的区域

一，两个颜色。
二，1种颜色一个联通区域，1种颜色超过1个连通区域。
矩形矩形起点、矩形终点、矩形各点，时间复杂度:O(N⁶)，超时的边缘。
可以优化到O(N⁵)
mat[r…r1][c1…c2]转移到mat[r…r1][c1…c2+1]，只需要处理一列，单个矩形处理时间O(N)。故总时间O(N⁵)。
新列的处理逻辑如下：
每列一个并集查找，本列有m个点，编号0 $\cdots$ m-1,前一列虚拟成一个节点m。本列相邻的点，如果颜色相同，相互连通；本列和上列同行的点，如果颜色相同，和m连通。除m所在的连通区域外，都是新增连通区域。第0列，无需特殊处理。
处理(r,c,r1,?)封装成函数Do:
v的各元素，有两个元素：颜色，区域数量。
cc = -1。
枚举c = c1 to N-1
{
处理各列
新颜色的连通区域加到v中。
如果v的颜色数>2，break;
如果颜色数是1,continue;
如果两个颜色的较小值iMin >1 break；
如果两个颜色的较大值iMax <=1 ,continue;
cc =c;
}
如果cc不是-1，(r,c,r1,cc)假定矩形结果中。
性质一：cc1 < cc2，则(r,c,r1,cc2)包括(r,c,r,cc1)，故删除后者。删除后矩形数量不超过O(NNN)。

处理包括

直接两两枚举矩形，时间复杂度：O(N⁶)。

错误原因

增益一列，连通区域可能减少。如下图，增加最后一列后，连通区域减少。
在这里插入图片描述

正确解法

改成O(N⁶)解法，用时最多的测试用例只用了71ms，时间限制是1s。
加了边后，枚举矩形各点，看有那些区域，再统计区域颜色。

代码

核心代码

#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<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1,class T2>inline CInBuff& operator>>(pair<T1,T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2,class T3>inline CInBuff& operator>>(tuple<T1, T2,T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3,class T4>inline CInBuff& operator>>(tuple<T1, T2, T3,T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for(int i = 0 ;i < canRead;i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size()){for (int i = 0; i < vNeiBo.size(); i++) {for (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}vector<int> GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize = m_vNodeToRegion.size();vector<int> vRet(iNodeSize);for (int i = 0; i < iNodeSize; i++){vRet[GetConnectRegionIndex(i)]++;}return vRet;}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:void UnionConnect(int iFrom, int iTo){m_vNodeToRegion[iFrom] = iTo;}vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;};
class Solution {
public:int Ans(const vector<vector<char>>& mat) {const int N = mat.size();vector<tuple<int, int, int, int>> rects;auto Do = [&](const int r, const int c, const int r1) {auto Mask = [&](int r, int c) {return N * r + c; };int cc = -1;CUnionFind uf(N * N);for (int c1 = c; c1 < N; c1++) {for (int r2 = r; r2 <= r1; r2++){if ((c1 > c) && (mat[r2][c1] == mat[r2][c1 - 1])) {uf.Union(Mask(r2, c1), Mask(r2, c1 - 1));}if ((r2 > r) && (mat[r2][c1] == mat[r2 - 1][c1])) {uf.Union(Mask(r2, c1), Mask(r2 - 1, c1));}}vector<pair<int, int>> colors;auto AddColor = [&](int iColor) {for (auto& pr : colors) {if (iColor == pr.first) { pr.second++; return; }}colors.emplace_back(iColor, 1);};vector<bool> regs(N * N);for (int c2 = c; c2 <= c1; c2++) {for (int r2 = r; r2 <= r1; r2++){regs[uf.GetConnectRegionIndex(Mask(r2, c2))] = true;}}for (int i = 0; i < N * N; i++) {if (regs[i]) { AddColor(mat[i / N][i % N]); }}if (2 != colors.size()) { continue; }const int iMin = min(colors[0].second, colors[1].second);const int iMax = max(colors[0].second, colors[1].second);if ((1 == iMin) && (iMax > 1)) { cc = c1; }}if (-1 == cc) { return; }rects.emplace_back(r, c, r1, cc);};for (int r = 0; r < N; r++){for (int c = 0; c < N; c++) {for (int r1 = r; r1 < N; r1++) {Do(r, c, r1);}}}int ans = 0;for (const auto& [r1, c1, r2, c2] : rects) {int cnt = 0;for (const auto& [r3, c3, r4, c4] : rects) {cnt += ((r3 <= r1) && (c3 <= c1) && (r2 <= r4) && (c2 <= c4));}ans += (cnt == 1);}return ans;}
};int main() {	
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	CInBuff<> ib;int N;ib >> N  ;vector<vector<char>> mat(N);char tmp;for (int i = 0; i < N; i++) {mat[i] = ib.Read<char>(N); ib >> tmp;}
#ifdef _DEBUG		//printf("N=%d,", N);Out(mat, ",mat=");//Out(pos, ",pos=");/*Out(edge, "edge=");Out(que, "que=");*/
#endif // DEBUG	auto res = Solution().Ans(mat);cout << res;return 0;
}

代码

vector<vector<char>> mat;TEST_METHOD(TestMethod1){mat = { {'A','B','B','C'},{'B','B','B','C'},{'A','A','B','B'},{'A','B','B','C'} };auto res = Solution().Ans(mat);AssertEx(2, res);}

扩展阅读

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