#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int f[N][N][2],ans;
string s[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]=" "+s[i]; 
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j]=='G')
	{
        f[i][j][0]=(s[i][j-1]=='R'&&s[i][j+1]=='W');
        f[i][j][1]=(s[i-1][j]=='R'&&s[i+1][j]=='W');
        if(f[i-1][j+1][0]|f[i-1][j+1][1])
			f[i][j][0]&=f[i-1][j+1][0],f[i][j][1]&=f[i-1][j+1][1];
        ans+=f[i][j][0]|f[i][j][1];
    }
	cout<<ans;return 0;
}

简约风。

分析

首先想到二维前缀和，然后发现转移会算重，遂弃之。

启发考虑上述做法在什么条件下会算重，容易发现只有三种概型：

RGW    R       R
G     RGW      G
W      W     RGW

考虑处理交叉时选择横向串还是竖向串。

为了方便，用一个点表示一个串的位置，不妨举 $G$ 为串的象征点，可知每个 $G$ 点可能与其右上方的 $G$ 点产生冲突，设 $f_{i,j,0/1}$ 表示格子 $(i,j)$ 能否得到横向 $/$ 竖向串。

于是扫一遍 $n\times m$ 的网格，从右上方贪心转移 $f$，答案即 $\sum f_{i,j,0}|f_{i,j,1}$。

正确性显然，每个 $G$ 点只可能与右上方的 $G'$ 点冲突，如果 $G'$ 可以转向以使 $G$ 合法则必转向。

用 $R$ 或 $W$ 作象征点的转移同理。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=3e3+5;
int n,m,f[N][N][2],ans;
char s[N][N];
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%s",s[i]+1);
    rep(i,1,n) rep(j,1,m) if(s[i][j]=='G'){
        f[i][j][0]=(s[i][j-1]=='R'&&s[i][j+1]=='W');
        f[i][j][1]=(s[i-1][j]=='R'&&s[i+1][j]=='W');
        if(f[i-1][j+1][0]|f[i-1][j+1][1]) f[i][j][0]&=f[i-1][j+1][0],f[i][j][1]&=f[i-1][j+1][1];
        ans+=f[i][j][0]|f[i][j][1];
    }printf("%d",ans);
}