#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std ;
const int maxn = 3002 , maxq =1e6 , inf = 1e9 + 100 , mod = 1e9 + 7 ;
char c[maxn][maxn] ;
vector <int> G[maxq] ;
vector <int> vec[maxn][maxn] ;
int ans[2] , dp[maxn][2];
bool mark[maxq] ;
void dfs(int v ){
mark[v] = 1;
dp[v][1] = 1;
for(int i = 0 ; i < (int)G[v].size() ; i++){
int u = G[v][i] ;
if(mark[u] == 1)continue ;
dfs(u);
dp[v][0] += max(dp[u][1] , dp[u][0]) ;
dp[v][1] += dp[u][0] ;
}
}
signed main(){
int n , m ;
cin >> n >> m ;
for(int i = 1; i <= n ; i++){
for(int j = 1; j <= m ; j++){
cin >> c[i][j] ;
}
}
int cnt = 0 ;
for(int i =1 ; i <= n ; i++){
for(int j = 1; j <= m ; j++){
if(i <= (n-2) && c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
cnt++;
// cout << i << " " << j << "D\n";
vec[i][j].pb(cnt);
vec[i+1][j].pb(cnt);
vec[i+2][j].pb(cnt);
}
if(j <= (m-2) && c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
cnt++;
// cout << i << " " << j << "R\n";
vec[i][j].pb(cnt);
vec[i][j+1].pb(cnt);
vec[i][j+2].pb(cnt);
}
}
}
for(int i =1 ; i<= n ; i++){
for(int j = 1; j <= m ; j++){
if(vec[i][j].size() == 2){
int v = vec[i][j][0] , u = vec[i][j][1] ;
G[v].pb(u);
G[u].pb(v);
}
}
}
int ans1 = 0 ;
for(int i = 1 ;i <= cnt ; i++){
if(mark[i] == 1)continue ;
dfs(i);
ans1 += max(dp[i][0] , dp[i][1]);
}
cout << ans1 << "\n";
}
/*
5 3
RRR
RRG
RGW
GWR
WRR
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
235420 KB |
Output is correct |
2 |
Correct |
119 ms |
235336 KB |
Output is correct |
3 |
Correct |
112 ms |
235336 KB |
Output is correct |
4 |
Correct |
114 ms |
235332 KB |
Output is correct |
5 |
Correct |
113 ms |
235392 KB |
Output is correct |
6 |
Correct |
113 ms |
235332 KB |
Output is correct |
7 |
Correct |
114 ms |
235340 KB |
Output is correct |
8 |
Correct |
115 ms |
235424 KB |
Output is correct |
9 |
Correct |
112 ms |
235336 KB |
Output is correct |
10 |
Correct |
114 ms |
235400 KB |
Output is correct |
11 |
Correct |
124 ms |
235544 KB |
Output is correct |
12 |
Correct |
115 ms |
235380 KB |
Output is correct |
13 |
Correct |
118 ms |
235428 KB |
Output is correct |
14 |
Correct |
127 ms |
235340 KB |
Output is correct |
15 |
Correct |
120 ms |
235304 KB |
Output is correct |
16 |
Correct |
114 ms |
235340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
235420 KB |
Output is correct |
2 |
Correct |
119 ms |
235336 KB |
Output is correct |
3 |
Correct |
112 ms |
235336 KB |
Output is correct |
4 |
Correct |
114 ms |
235332 KB |
Output is correct |
5 |
Correct |
113 ms |
235392 KB |
Output is correct |
6 |
Correct |
113 ms |
235332 KB |
Output is correct |
7 |
Correct |
114 ms |
235340 KB |
Output is correct |
8 |
Correct |
115 ms |
235424 KB |
Output is correct |
9 |
Correct |
112 ms |
235336 KB |
Output is correct |
10 |
Correct |
114 ms |
235400 KB |
Output is correct |
11 |
Correct |
124 ms |
235544 KB |
Output is correct |
12 |
Correct |
115 ms |
235380 KB |
Output is correct |
13 |
Correct |
118 ms |
235428 KB |
Output is correct |
14 |
Correct |
127 ms |
235340 KB |
Output is correct |
15 |
Correct |
120 ms |
235304 KB |
Output is correct |
16 |
Correct |
114 ms |
235340 KB |
Output is correct |
17 |
Correct |
118 ms |
235408 KB |
Output is correct |
18 |
Correct |
114 ms |
235408 KB |
Output is correct |
19 |
Correct |
115 ms |
235516 KB |
Output is correct |
20 |
Correct |
112 ms |
235420 KB |
Output is correct |
21 |
Correct |
108 ms |
235444 KB |
Output is correct |
22 |
Correct |
108 ms |
235452 KB |
Output is correct |
23 |
Correct |
126 ms |
235444 KB |
Output is correct |
24 |
Correct |
109 ms |
235448 KB |
Output is correct |
25 |
Correct |
107 ms |
235416 KB |
Output is correct |
26 |
Correct |
110 ms |
235392 KB |
Output is correct |
27 |
Incorrect |
112 ms |
235380 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
235420 KB |
Output is correct |
2 |
Correct |
119 ms |
235336 KB |
Output is correct |
3 |
Correct |
112 ms |
235336 KB |
Output is correct |
4 |
Correct |
114 ms |
235332 KB |
Output is correct |
5 |
Correct |
113 ms |
235392 KB |
Output is correct |
6 |
Correct |
113 ms |
235332 KB |
Output is correct |
7 |
Correct |
114 ms |
235340 KB |
Output is correct |
8 |
Correct |
115 ms |
235424 KB |
Output is correct |
9 |
Correct |
112 ms |
235336 KB |
Output is correct |
10 |
Correct |
114 ms |
235400 KB |
Output is correct |
11 |
Correct |
124 ms |
235544 KB |
Output is correct |
12 |
Correct |
115 ms |
235380 KB |
Output is correct |
13 |
Correct |
118 ms |
235428 KB |
Output is correct |
14 |
Correct |
127 ms |
235340 KB |
Output is correct |
15 |
Correct |
120 ms |
235304 KB |
Output is correct |
16 |
Correct |
114 ms |
235340 KB |
Output is correct |
17 |
Correct |
118 ms |
235408 KB |
Output is correct |
18 |
Correct |
114 ms |
235408 KB |
Output is correct |
19 |
Correct |
115 ms |
235516 KB |
Output is correct |
20 |
Correct |
112 ms |
235420 KB |
Output is correct |
21 |
Correct |
108 ms |
235444 KB |
Output is correct |
22 |
Correct |
108 ms |
235452 KB |
Output is correct |
23 |
Correct |
126 ms |
235444 KB |
Output is correct |
24 |
Correct |
109 ms |
235448 KB |
Output is correct |
25 |
Correct |
107 ms |
235416 KB |
Output is correct |
26 |
Correct |
110 ms |
235392 KB |
Output is correct |
27 |
Incorrect |
112 ms |
235380 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |