#include<bits/stdc++.h>
#define MAXN 6000007
using namespace std;
struct edge{
int to,flow,cap,rev;
};
int n,m;
char t[3007][3007];
vector<edge> v[MAXN];
int s[MAXN],cnt1,cnt2,ans;
int num[3007][3007],num2[3007][3007],total;
int flow,maxflow,source,sink;
int li[MAXN],tim;
void add_edge(int from,int to){
v[from].push_back({to,0,1,v[to].size()});
v[to].push_back({from,0,0,v[from].size()-1});
}
int dfs(int x,int mins){
if(x==sink)return mins;
li[x]=tim;
for(int i=0;i<v[x].size();i++){
if(li[v[x][i].to]==tim or v[x][i].cap-v[x][i].flow<=0)continue;
int curr=dfs(v[x][i].to,1);
if(curr>0){
v[x][i].flow+=curr;
v[v[x][i].to][v[x][i].rev].flow-=curr;
return curr;
}
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<=n+1;i++){
for(int f=0;f<=m+1;f++){
t[i][f]='#';
}
}
for(int i=1;i<=n;i++){
for(int f=1;f<=m;f++){
cin>>t[i][f];
}
}
source=0; sink=2*n*m/3;
for(int i=1;i<=n;i++){
for(int f=1;f<=m;f++){
if(t[i][f]=='R' and t[i][f+1]=='G' and t[i][f+2]=='W'){
total++; num[i][f]=total;
add_edge(source,total);
}
if(t[i][f]=='R' and t[i+1][f]=='G' and t[i+2][f]=='W'){
total++; num2[i][f]=total;
add_edge(total,sink);
}
if(t[i][f]=='R' and t[i][f+1]=='G' and t[i][f+2]=='W' and t[i+1][f]=='G' and t[i+2][f]=='W'){
add_edge(num[i][f],num2[i][f]);
}
}
}
for(int i=1;i<=n;i++){
for(int f=1;f<=m;f++){
if(t[i][f]=='G' and t[i][f-1]=='R' and t[i][f+1]=='W' and t[i-1][f]=='R' and t[i+1][f]=='W'){
add_edge(num[i][f-1],num2[i-1][f]);
}
}
}
for(int i=2;i<=n;i++){
for(int f=2;f<=m;f++){
if(t[i][f]=='W' and t[i][f-2]=='R' and t[i][f-1]=='G' and t[i-2][f]=='R' and t[i-1][f]=='G'){
add_edge(num[i][f-2],num2[i-2][f]);
}
}
}
while(true){
tim++;
flow=dfs(source,1);
if(flow==0)break;
maxflow+=flow;
if(maxflow>total)exit(0);
}
cout<<total-maxflow<<"\n";
return 0;
}
Compilation message
dango_maker.cpp: In function 'void add_edge(int, int)':
dango_maker.cpp:20:41: warning: narrowing conversion of 'v[to].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
20 | v[from].push_back({to,0,1,v[to].size()});
| ~~~~~~~~~~^~
dango_maker.cpp:21:45: warning: narrowing conversion of '(v[from].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
21 | v[to].push_back({from,0,0,v[from].size()-1});
| ~~~~~~~~~~~~~~^~
dango_maker.cpp: In function 'int dfs(int, int)':
dango_maker.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
143952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
143952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
143952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
