#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define _all(a) a.begin(),a.end()
#define pii pair<int,int>
const int mxn = 3030;
struct Edge{
int to;
int cap;
Edge(){}
Edge(int tt,int cc){
to = tt,cap = cc;
}
};
vector<Edge> edges;
bitset<mxn> done[mxn];
vector<vector<int>> paths;
vector<int> level;
string s[mxn];
int st,ed;
void addedge(int a,int b){
paths[a].push_back(edges.size());
edges.push_back(Edge(b,1));
paths[b].push_back(edges.size());
edges.push_back(Edge(a,0));
}
bool bfs(){
queue<int> q;
fill(level.begin(),level.end(),-1);
level[0] = 0;
q.push(0);
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto &id:paths[now]){
if(!edges[id].cap)continue;
auto nxt = edges[id].to;
if(level[nxt] == -1){
level[nxt] = level[now]+1;
q.push(nxt);
}
}
}
return level[ed] != -1;
}
int dfs(int now,int lim){
if(now == ed)return lim;
int ans = 0;
for(auto &id:paths[now]){
if(!edges[id].cap)continue;
if(!lim)break;
auto nxt = edges[id].to;
if(level[nxt] != level[now]+1)continue;
auto re = dfs(nxt,min(edges[id].cap,lim));
if(re == 0)continue;
edges[id].cap -= re;
edges[id^1].cap += re;
ans += re;
lim -= re;
}
return ans;
}
vector<pii> righ,down;
int n,m;
int calc(int x,int y){
//cout<<x<<y<<endl;
righ.clear();
down.clear();
queue<pii> q;
q.push(make_pair(x,y));
done[x][y] = true;
while(!q.empty()){
auto now = q.front();
q.pop();
done[now.fs][now.sc] = true;
if(now.sc<m-2&&s[now.fs].substr(now.sc,3)=="RGW"){
righ.push_back(now);
pii nxt = make_pair(now.fs-1,now.sc+1);
if(nxt.fs>=0&&nxt.sc<m&&now.fs<n-2&&!done[nxt.fs][nxt.sc]&&s[nxt.fs][nxt.sc] == 'R'&&
s[nxt.fs+1][nxt.sc] == 'G'&&s[nxt.fs+2][nxt.sc] == 'W'){
done[nxt.fs][nxt.sc] = true;
q.push(nxt);
}
nxt = make_pair(now.fs-2,now.sc+2);
if(nxt.fs>=0&&nxt.sc<m&&now.fs<n-2&&!done[nxt.fs][nxt.sc]&&s[nxt.fs][nxt.sc] == 'R'&&
s[nxt.fs+1][nxt.sc] == 'G'&&s[nxt.fs+2][nxt.sc] == 'W'){
done[nxt.fs][nxt.sc] = true;
q.push(nxt);
}
}
if(now.fs<n-2&&s[now.fs][now.sc] == 'R'&&s[now.fs+1][now.sc] == 'G'&&s[now.fs+2][now.sc] == 'W'){
down.push_back(now);
pii nxt = make_pair(now.fs+1,now.sc-1);
if(nxt.fs<n-2&&nxt.sc>0&&nxt.sc<m-2&&s[nxt.fs].substr(nxt.sc,3)=="RGW"&&!done[nxt.fs][nxt.sc]){
done[nxt.fs][nxt.sc] = true;
q.push(nxt);
}
nxt = make_pair(now.fs+2,now.sc-2);
if(nxt.fs<n-2&&nxt.sc>0&&nxt.sc<m-2&&s[nxt.fs].substr(nxt.sc,3)=="RGW"&&!done[nxt.fs][nxt.sc]){
done[nxt.fs][nxt.sc] = true;
q.push(nxt);
}
}
}
paths = vector<vector<int>>(down.size()+righ.size()+2);
level = vector<int>(paths.size());
sort(down.begin(),down.end());
sort(righ.begin(),righ.end());
for(int i = 0;i<down.size();i++){
pii tar = make_pair(down[i].fs,down[i].sc);
auto pos = lower_bound(_all(righ),tar)-righ.begin();
if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
tar = make_pair(down[i].fs+1,down[i].sc-1);
pos = lower_bound(_all(righ),tar)-righ.begin();
if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
tar = make_pair(down[i].fs+2,down[i].sc-2);
pos = lower_bound(_all(righ),tar)-righ.begin();
if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
}
for(int i = 1;i<=down.size();i++)addedge(0,i);
for(int i = down.size()+1;i<paths.size()-1;i++)addedge(i,paths.size()-1);
int ans = 0;
//cout<<paths.size()<<endl<<endl;
/*
for(int i = 0;i<paths.size();i++){
for(auto &id:paths[i]){
cout<<i<<','<<edges[id].to<<' ';
}
}
*/
ed = paths.size()-1;
st = 0;
while(bfs()){
int re = 0;
while(re = dfs(0,mxn*mxn))ans+= re;
//cout<<re<<endl;
}
//cout<<"HI"<<endl;
return (int)down.size()+righ.size()-ans;
}
void solve(){
cin>>n>>m;
int ans = 0;
for(int i = 0;i<n;i++)cin>>s[i];
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(done[i][j])continue;
//cout<<i<<' '<<j<<endl;
if(j<m-2&&s[i].substr(j,3)=="RGW")ans += calc(i,j);
else if(i<n-2&&s[i][j] == 'R'&&s[i+1][j] == 'G'&&s[i+2][j] == 'W')ans += calc(i,j);
}
}
cout<<ans;
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}
Compilation message
dango_maker.cpp: In function 'int calc(int, int)':
dango_maker.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i = 0;i<down.size();i++){
| ~^~~~~~~~~~~~
dango_maker.cpp:125:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
| ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:128:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
| ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:131:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
| ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:133:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int i = 1;i<=down.size();i++)addedge(0,i);
| ~^~~~~~~~~~~~~
dango_maker.cpp:134:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = down.size()+1;i<paths.size()-1;i++)addedge(i,paths.size()-1);
| ~^~~~~~~~~~~~~~~
dango_maker.cpp:149:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
149 | while(re = dfs(0,mxn*mxn))ans+= re;
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
