题意简述

给定一个字符矩阵，统计矩阵中出现子串 ROG 的数量。

解题思路

本题使用二维前缀和的思想，方式记录每个位置处 R、RO、ROG 的数量，避免暴力遍历，将复杂度优化到 O(nm)。

总体逻辑

• R[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 R 的总个数。
• RO[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 RO 的总个数。
• ROG[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 ROG 的总个数。

C++代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
const int N = 2005;
char a[N][N];	// 记录要输入的字符矩阵  
int R[N][N];	// 从(1,1)到(i,j)，出现了多少个"R"
int RO[N][N];	// 从(1,1)到(i,j)，出现了多少组"RO" 
int ROG[N][N];	// 从(1,1)到(i,j)，出现了多少组"ROG" 
int n, m;
string s;
int ans;

int funcRO( int i, int j ){	// 判断这个位置是不是"O" 
	if( a[i][j] == 'O' )
		return R[i][j];		// 当前是'O'，再加上之前的'R'的数量，就是当前有多少组"RO"
	return 0;
}
int funcROG( int i, int j ){ // 判断这个位置是不是"G"
	if( a[i][j] == 'G' )
		return RO[i][j];	// 当前是'G'，再加上之前的'RO'的数量，就是当前有多少组"ROG"
	return 0;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0); 
	cin >> n >> m;
	for( int i = 1; i <= n; i++ ){
		cin >> s;
		s = " " + s;	// 将字符串中的每一个字符存入字符矩阵a的对应位置 (最好从下标 1 开始) 
		for( int j = 1; j <= m; j++ ){
			a[i][j] = s[j];	// 字符串中的每一位放到二维字符数组这一行的每一位上  
		}
	}
	// 构建二维前缀和 
	for( int i = 1; i <= n; i++ ){
		for( int j = 1; j <= m; j++ ){
			// 枚举到每一个位置时，前缀和中都要记入数据    
			R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + (a[i][j] == 'R');
			RO[i][j] = RO[i-1][j] + RO[i][j-1] - RO[i-1][j-1] + funcRO( i, j );
			ROG[i][j] = ROG[i-1][j] + ROG[i][j-1] - ROG[i-1][j-1] + funcROG( i, j );
		}
	}
	// ROG[n][m]就是从(1,1)到(n,m)出出现了多少组"ROG" 
	ans = ROG[n][m] % MOD;
	cout << ans;
	return 0;
}