题解

#include<bits/stdc++.h>
using namespace std;
const int N=9e6+10,M=9e6+10,inf=0x3f3f3f3f,s=0;
int n,m,t,cnt,tot=1,ans,head[N],now[N],dis[N],use[3010][3010];char S[3010][3010];
struct edge{int to,nxt,w;}e[M<<1];
inline void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
inline void Add(int u,int v,int w){add(u,v,w),add(v,u,0);}
inline bool bfs(int s,int t){
    queue<int>q;for(int i=0;i<=cnt;i++)dis[i]=inf;
    q.push(s),dis[s]=0,now[s]=head[s];
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(e[i].w&&dis[y]==inf){
                q.push(y),dis[y]=dis[x]+1,now[y]=head[y];
                if(y==t)return 1;
            }
        }
    }return 0;
}int dfs(int x,int sum){
    if(x==t)return sum;
    int k,ret=0;
    for(int i=now[x];i&&sum;i=e[i].nxt){
        now[x]=i;int y=e[i].to;
        if(e[i].w&&dis[y]==dis[x]+1){
            k=dfs(y,min(sum,e[i].w));
            if(!k)dis[y]=inf;
            e[i].w-=k,e[i^1].w+=k,sum-=k,ret+=k;
        }
    }return ret;
}void dinic(){while(bfs(s,t))ans+=dfs(s,inf);}
int main(){
    ios::sync_with_stdio(cin.tie(cout.tie()));
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>S[i][j];
    for(int i=1;i<=n-2;i++)for(int j=1;j<=m;j++)if(S[i][j]=='R'&&S[i+1][j]=='G'&&S[i+2][j]=='W')Add(s,++cnt,1),use[i][j]=use[i+1][j]=use[i+2][j]=cnt;
    int tmp=cnt+1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m-2;j++)if(S[i][j]=='R'&&S[i][j+1]=='G'&&S[i][j+2]=='W'){
        ++cnt;
        if(use[i][j])Add(use[i][j],cnt,1);
        if(use[i][j+1])Add(use[i][j+1],cnt,1);
        if(use[i][j+2])Add(use[i][j+2],cnt,1);
    }t=++cnt;
    for(int i=tmp;i<cnt;i++)Add(i,t,1);
    return dinic(),cout<<cnt-1-ans,0;
}