#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf = (int)1e9 + 123, N = (int)3e3 + 5, M = N;
int n, m;
char c[N][M];
struct MaxFlow {
int nVer, src, snk;
struct Edge {
int u, v, cap, f;
Edge(int _u, int _v, int _cap, int _f) : u(_u), v(_v), cap(_cap), f(_f) {}
};
vector< vector<int> > gr;
vector<Edge> edge;
vector<int> d, iGr;
MaxFlow(int _nVer = 0, int _src = 0, int _snk = 0) : nVer(_nVer), src(_src), snk(_snk) { edge.clear(); gr.assign(nVer + 5, vector<int>() ); }
void addEdge(int u, int v, int cap) {
gr[u].pb( (int)edge.size() ); edge.pb(Edge(u, v, cap, 0) );
gr[v].pb( (int)edge.size() ); edge.pb(Edge(v, u, 0, 0) );
}
bool bfs() {
d.assign(nVer + 5, inf); d[src] = 0; iGr.assign(nVer + 5, 0);
queue<int> q; q.push(src);
while(!q.empty() ) {
int u = q.front(); q.pop();
for (int id : gr[u]) if(d[ edge[id].v ] == inf && edge[id].f < edge[id].cap) d[ edge[id].v ] = d[u] + 1, q.push(edge[id].v);
}
return d[snk] != inf;
}
int dfs(int u, int flow) {
if(u == snk || !flow) return flow;
for (int &i = iGr[u]; i < (int)gr[u].size(); ++i) {
int id = gr[u][i];
if(d[ edge[id].v ] != d[u] + 1 || edge[id].f >= edge[id].cap) continue;
int nex = dfs(edge[id].v, min(flow, edge[id].cap - edge[id].f) );
if(nex) { edge[id].f += nex; edge[id ^ 1].f -= nex; return nex; }
}
return 0;
}
int solve() {
while(bfs() ) while(dfs(src, inf) );
int ret = 0;
for (int id : gr[src]) ret += edge[id].f;
return ret;
}
};
int _1D (int x, int y) { return (x - 1) * m + y; }
int prv (int x, int y) { return _1D(x, y); }
int nxt (int x, int y) { return _1D(x, y) + n * m; }
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) cin >> c[i][j];
}
MaxFlow mf(2 + 2 * n * m, 0, 1 + 2 * n * m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
mf.addEdge(prv(i, j), nxt(i, j), 1);
if (c[i][j] == 'R') mf.addEdge(mf.src, prv(i, j), 1);
if (c[i][j] == 'W') mf.addEdge(nxt(i, j), mf.snk, 1);
if (c[i][j] == 'R' && c[i][j + 1] == 'G') mf.addEdge(nxt(i, j), prv(i, j + 1), 1);
if (c[i][j] == 'R' && c[i + 1][j] == 'G') mf.addEdge(nxt(i, j), prv(i + 1, j), 1);
if (c[i][j] == 'G' && c[i][j + 1] == 'W') mf.addEdge(nxt(i, j), prv(i, j + 1), 1);
if (c[i][j] == 'G' && c[i + 1][j] == 'W') mf.addEdge(nxt(i, j), prv(i + 1, j), 1);
}
}
cout << mf.solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
