#include<bits/stdc++.h>
#define MAXN 7000007
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,dist[MAXN],ind[MAXN];
queue<int> q;
void add_edge(int from,int to){
v[from].push_back({to,0,1,int(v[to].size())});
v[to].push_back({from,0,0,int(v[from].size())-1});
}
void bfs(int x){
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;
q.push(v[x][i].to);
li[v[x][i].to]=tim;
dist[v[x][i].to]=dist[x]+1;
}
}
void do_bfs(){
tim++; li[source]=tim;
q.push(source);
while(!q.empty()){
bfs(q.front());
q.pop();
}
}
int dfs(int x,int mins){
if(x==sink)return mins;
if(li[x]!=tim)ind[x]=0;
li[x]=tim;
for(int i=ind[x];i<v[x].size();i++){
if(dist[v[x][i].to]!=dist[x]+1 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;
}
ind[x]++;
i=max(i,ind[x]-1);
}
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=3*n*m/4;
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){
do_bfs();
if(li[sink]!=tim)break;
tim++;
while(true){
flow=dfs(source,1);
if(flow==0)break;
maxflow+=flow;
}
}
cout<<total-maxflow<<"\n";
return 0;
}
Compilation message
dango_maker.cpp: In function 'void bfs(int)':
dango_maker.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dango_maker.cpp: In function 'int dfs(int, int)':
dango_maker.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=ind[x];i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
168548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
168548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
168548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
