#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int has[3000][3000][2];
int n,m;
bool valid(int x, int y){
if(x>=0 && x<n && y>=0 && y<m)return true;
return false;
}
bool visited[10000000];
int size;
int independent;
vector<int> graph[10000000];
queue<int> q;
vector<int> tree[10000000];
int DP[10000000][2];
void DFS(int node){
visited[node]=true;
//q.push(node);
trav(v,graph[node]){
if(!visited[v]){
tree[node].push_back(v);
DFS(v);
}
}
}
int compute(int node, int x){
if(DP[node][x]!=-1)return DP[node][x];
DP[node][x]=0;
if(x==0){
trav(v,tree[node]){
DP[node][x]+=max(compute(v,0),compute(v,1));
}
return DP[node][x];
}
DP[node][x]++;
trav(v,tree[node]){
DP[node][x]+=compute(v,0);
}
return DP[node][x];
}
int main(){
cin>>n>>m;
string table[n];
rep(i,0,n){
cin>>table[i];
}
int V=0;
int H=0;
vector<pii> v;
vector<pii> h;
rep(i,0,n){
rep(j,0,m){
has[i][j][0]=-1;
has[i][j][1]=-1;
if(table[i][j]=='R'){
if(i+2<n && table[i+1][j]=='G' && table[i+2][j]=='W'){
has[i][j][0]=V;
V++;
v.push_back(pii(i,j));
}
if(j+2<m && table[i][j+1]=='G' && table[i][j+2]=='W'){
has[i][j][1]=H;
H++;
h.push_back(pii(i,j));
}
}
}
}
rep(i,0,n){
rep(j,0,m){
if(has[i][j][0]!=-1){
if(has[i][j][1]!=-1){
graph[has[i][j][0]].push_back(has[i][j][1]+V);
graph[has[i][j][1]+V].push_back(has[i][j][0]);
}
if(valid(i+1,j-1) && has[i+1][j-1][1]!=-1){
graph[has[i][j][0]].push_back(has[i+1][j-1][1]+V);
graph[has[i+1][j-1][1]+V].push_back(has[i][j][0]);
}
if(valid(i+2,j-2) && has[i+2][j-2][1]!=-1){
graph[has[i][j][0]].push_back(has[i+2][j-2][1]+V);
graph[has[i+2][j-2][1]+V].push_back(has[i][j][0]);
}
}
}
}
//cout<<V+H<<endl;
rep(i,0,V+H){
DP[i][0]=-1;
DP[i][1]=-1;
/*trav(v,graph[i]){
cout<<v<<" ";
}
cout<<endl;*/
}
rep(i,0,V+H){
visited[i]=false;
}
int ans=0;
rep(i,0,V+H){
if(!visited[i]){
DFS(i);
/*while(!q.empty()){
//if(q.front()<V)cout<<v[q.front()].first<<","<<v[q.front()].second<<" ";
//if(q.front()>=V)cout<<h[q.front()-V].first<<","<<h[q.front()-V].second<<" ";
visited[q.front()]=false;
q.pop();
}//cout<<endl;*/
ans+=max(compute(i,0),compute(i,1));
//cout<<independent<<" "<<size-independent<<"A"<<endl;
}
}
/*rep(i,0,V+H){
cout<<compute(i,0)<<" "<<compute(i,1)<<endl;
}*/
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
