【圖論并集查找】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);}

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功