#include "bits/stdc++.h"
using namespace std;
using ll = long long;
// RGW
template<class T>
struct dinic {
static constexpr T INF = numeric_limits<T>::max();
struct edge {
int v, r; T c;
edge(int _v, int _r, T _c) : v{_v}, r{_r}, c{_c} {}
};
int n, s, t;
vector<vector<edge>> G;
vector<int> d, arc;
dinic(int _n, int _s, int _t) : n{_n}, s{_s}, t{_t}, G(_n) {}
void add_edge(int u, int v, T c) {
G[u].emplace_back(v, (int)G[v].size(), c);
G[v].emplace_back(u, (int)G[u].size() - 1, 0);
}
int bfs() {
d.assign(n, 0), arc.assign(n, 0);
queue<int> q;
d[s] = 1, q.emplace(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, r, c] : G[u]) {
if (!d[v] && c) {
d[v] = d[u] + 1;
if (v == t) return 1;
q.emplace(v);
}
}
}
return d[t];
}
T dfs(int u, T f) {
if (u == t) return f;
T sum = 0;
for (int& i = arc[u]; i < (int)G[u].size(); ++i) {
auto& [v, r, c] = G[u][i];
if (d[v] == d[u] + 1 && c) {
T res = dfs(v, min(f, c));
if (res) {
c -= res, G[v][r].c += res;
sum += res, f -= res;
if (!f) return sum;
} else {
d[v] = 0;
}
}
}
return sum;
}
T max_flow() {
T sum = 0;
while (bfs()) {
while (T res = dfs(s, INF)) {
sum += res;
}
}
return sum;
}
};
// bool dfs(int cur) {
// for (int nxt : va[cur]) {
// if (!visitb[nxt]) {
// visitb[nxt] = true;
// clrS.push(nxt);
// if (mb[nxt] == 0 || dfs(mb[nxt])) {
// ma[cur] = nxt;
// mb[nxt] = cur;
// return true;
// }
// }
// }
// return false;
// }
// int bipartite_matching() {
// memset(ma, -1, sizeof(ma));
// memset(mb, -1, sizeof(mb));
// int ret = 0;
// for (int i = 1; i <= cnt; i++) {
// while (!clrS.empty()) {
// visitb[clrS.top()] = false;
// clrS.pop();
// }
// if (dfs(i)) ++ret;
// }
// return ret;
// }
int main() {
int n, m;
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int cnt, cnt2;
cnt = cnt2 = 0;
// vector a(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != 'R') continue;
if (j + 2 < m) {
if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
++cnt;
// a[i][j] = cnt;
// a[i][j + 1] = cnt;
// a[i][j + 2] = cnt;
}
}
if (i + 2 < n) {
if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
++cnt2;
// b[i][j]= cnt2;
// b[i + 1][j]= cnt2;
// b[i + 2][j]= cnt2;
}
}
}
}
// return 0;
dinic<int> D(cnt + cnt2 + 2, 0, 1);
for (int i = 1; i <= cnt; i++) {
D.add_edge(0, i + 1, 1);
}
for (int i = 1; i <= cnt2; i++) {
D.add_edge(cnt + i + 1, 1, 1);
}
int cnt3 = 0;
int cnt4 = 0;
for (int k = 0; k < n + m - 1; k++) {
int prevcnt = -200;
int prevdex = -200;
int prevcnt2 = -200;
int prevdex2 = -200;
for (int i = max(0, k - m + 1); i < min(n, k + 1); i++) {
int j = k - i;
if (s[i][j] != 'R') continue;
if (j + 2 < m) {
if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
++cnt3;
if (prevdex == i - 1 || prevdex == i - 2) {
D.add_edge(cnt3 + 1, cnt + prevcnt + 1, D.INF);
// cout << prevdex << " -> " << i << endl;
}
if (prevdex2 == i - 2) {
D.add_edge(cnt3 + 1, cnt + prevcnt2 + 1, D.INF);
// cout << prevdex2 << " -> " << i << endl;
}
if (i + 2 < n && s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
D.add_edge(cnt3 + 1, cnt + cnt4 + 1 + 1, D.INF);
// cout << i << " -> " << i << endl;
}
// b[i][j]= cnt2;
// b[i + 1][j]= cnt2;
// b[i + 2][j]= cnt2;
}
}
if (i + 2 < n) {
if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
++cnt4;
swap(prevcnt, prevcnt2);
swap(prevdex, prevdex2);
prevcnt = cnt3;
prevdex = i;
// a[i][j] = cnt;
// a[i][j + 1] = cnt;
// a[i][j + 2] = cnt;
}
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (a[i][j] != 0 && b[i][j] != 0) {
// D.add_edge(a[i][j] + 1, cnt + b[i][j] + 1, D.INF);
// // va[a[i][j]].push_back(b[i][j]);
// }
// }
// }
cout << cnt + cnt2 - D.max_flow() << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
