#include "bits/stdc++.h"
using namespace std;
#define ln '\n'
const int N = 3e3 + 5;
const string S = "RGW";
struct hhh{
int horiz = -1, vert = -1;
} a[N][N];
int n, m, glit = 1;
string grid[N];
vector<int> adj[N*N/3];
bool vis[N*N/3];
int dp[N*N/3][2];
void dfs(int u, int p){
int take = 0, no_take = 0;
vis[u] = 1;
for (auto v: adj[u]){
if (v == p) continue;
dfs(v, u);
take += dp[v][1];
no_take += dp[v][0];
}
dp[u][0] = take;
dp[u][1] = 1 + no_take;
}
void solve(){
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> grid[i];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
bool ok = true;
for (int k = 0; k <= 2; k++){
int ti = i, tj = j + k;
if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;}
if (grid[ti][tj] != S[k]) {ok = false; break;}
}
if (ok) a[i][j+1].horiz = glit++;
ok = true;
for (int k = 0; k <= 2; k++){
int ti = i+k, tj = j;
if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;}
if (grid[ti][tj] != S[k]) {ok = false; break;}
}
if (ok) a[i+1][j].vert = glit++;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
int u = a[i][j].horiz, v = a[i][j].vert;
if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u);
if (i+1 >= n || j-1 < 0) continue;
u = a[i][j].horiz, v = a[i+1][j-1].vert;
if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u);
// cout << u << ' ' << v << ln;
}
}
// maximum independent set in this forest
int ans = 0;
for (int i = 1; i < glit; i++){
if (vis[i]) continue;
dfs(i, -1);
ans += max(dp[i][0], dp[i][1]);
}
cout << ans << ln;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Compilation message
Compilation timeout while compiling dango_maker
