#include <bits/stdc++.h>
#include <crtdbg.h>
#pragma GCC optimize ("03")
#define pb push_back
#define INF 987654321
using namespace std;
typedef long long LL;
int n, m, x;
vector<char> str[3010];
int ans;
vector<int> id;
vector<int> par;
vector<bool> used;
vector<int> dist, A, B;
vector<vector<int> > vc, link;
vector<vector<vector<int> > >col;
unordered_map<int, int> mp;
queue<int> Q;
int findpar(int num)
{
if(num==par[num])return num;
return par[num]=findpar(par[num]);
}
void mergepar(int a, int b)
{
a=findpar(a);
b=findpar(b);
par[a]=par[b];
}
void bfs(int p)
{
for(int i=0; i<vc[p].size(); i++){
if(!used[i]){
dist[i]=0;
Q.push(i);
}
else dist[i]=INF;
}
while(!Q.empty()){
int a=Q.front();
Q.pop();
for(int b: link[vc[p][a]]){
b=mp[b];
if(B[b]!=-1&&dist[B[b]]==INF){
dist[B[b]]=dist[a]+1;
Q.push(B[b]);
}
}
}
}
bool dfs(int p, int a){
for(int b: link[vc[p][a]]){
b=mp[b];
if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
used[a]=true;
A[a]=b;
B[b]=a;
return true;
}
}
return false;
}
int hopcroft_carp(int p)
{
int match=0;
while(1){
bfs(p);
int flow=0;
for(int i=0; i<vc[p].size(); i++)
if(!used[i]&&dfs(p, i))flow++;
if(!flow)break;
match+=flow;
}
return match/2;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
str[i].pb(0);
for(int j=1; j<=m; j++){
char y;
scanf(" %c", &y);
str[i].pb(y);
}
}
col.resize(n+1);
for(int i=1; i<=n; i++)col[i].resize(m+1);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j+2<=m)
if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
++x;
col[i][j].pb(x);
col[i][j+1].pb(x);
col[i][j+2].pb(x);
}
if(i+2<=n)
if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
++x;
col[i][j].pb(x);
col[i+1][j].pb(x);
col[i+2][j].pb(x);
}
}
}
if(x>3000000)while(1){}
for(int i=1; i<=n; i++){
str[i].clear();
vector<char>().swap(str[i]);
}
link.resize(x+1);
for(int i=1; i<=x; i++)link[i].resize(3, -1);
for(int i=0; i<=x; i++)par.pb(i);
int kill=0;
for(int i=1; i<=n; j++)
for(int j=1; j<=m; j++)
if(col[i][j].size()==2)kill+=2;
if(kill>=3000000)while(1){}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(col[i][j].size()==2){
mergepar(col[i][j][1], col[i][j][0]);
if(link[col[i][j][1]][0]==-1)link[col[i][j][1]][0]=col[i][j][0];
else if(link[col[i][j][1]][1]==-1)link[col[i][j][1]][1]=col[i][j][0];
else if(link[col[i][j][1]][2]==-1)link[col[i][j][1]][2]=col[i][j][0];
if(link[col[i][j][0]][0]==-1)link[col[i][j][0]][0]=col[i][j][1];
else if(link[col[i][j][0]][1]==-1)link[col[i][j][0]][1]=col[i][j][1];
else if(link[col[i][j][0]][2]==-1)link[col[i][j][0]][2]=col[i][j][1];
}
}
}
col.clear();
vector<vector<vector<int> > >().swap(col);
for(int i=1; i<=x; i++){
id.pb(findpar(i));
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
int maxpar=1;
for(int i=1; i<=x; i++){
par[i]=lower_bound(id.begin(), id.end(), par[i])-id.begin();
maxpar=max(maxpar, par[i]+1);
}
id.clear();
vector<int>().swap(id);
vc.resize(maxpar);
for(int i=1; i<=x; i++){
vc[par[i]].pb(i);
}
par.clear();
vector<int>().swap(par);
for(int i=0; i<maxpar; i++){
if(vc[i].size()==1)ans++;
else{
for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
used.resize(vc[i].size()+2);
dist.resize(vc[i].size()+2);
A.resize(vc[i].size()+2);
B.resize(vc[i].size()+2);
for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
ans+=vc[i].size()-hopcroft_carp(i);
mp.clear();
dist.clear();
A.clear();
B.clear();
used.clear();
vector<int>().swap(dist);
vector<int>().swap(A);
vector<int>().swap(B);
vector<bool>().swap(used);
}
}
printf("%d", ans);
_CrtDumpMemoryLeaks();
}
Compilation message
dango_maker.cpp:2:10: fatal error: crtdbg.h: No such file or directory
#include <crtdbg.h>
^~~~~~~~~~
compilation terminated.
