#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
const int NMAX = 3000;
char a[NMAX][NMAX];
std::vector<int> g[NMAX * NMAX];
bool vis[NMAX * NMAX];
int l[NMAX], r[NMAX];
bool cupleaza(int u) {
vis[u] = true;
for (const auto &v : g[u]) {
if (r[v] == -1) {
r[v] = u;
l[u] = v;
return true;
}
}
for (const auto &v : g[u]) {
if (!vis[r[v]] && cupleaza(r[v])) {
l[u] = v;
r[v] = u;
return true;
}
}
return false;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < n; i++) {
std::string s;
std::cin >> s;
for (int j = 0; j < m; j++) {
a[i][j] = s[j];
}
}
std::vector<int> vertl, vertr;
std::vector<std::pair<int, int>> edges;
int answer = 0;
for (int i = 0; i + 2 < n; i++) {
for (int j = 0; j + 2 < m; j++) {
if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
int id1 = i * m + j;
int id2 = id1 + n * m;
vertl.push_back(id1);
vertr.push_back(id2);
edges.push_back({id1, id2});
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((j + 2 < m && a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') ^ (i + 2 < n && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W')) {
answer++;
}
}
}
std::sort(vertl.begin(), vertl.end());
vertl.erase(std::unique(vertl.begin(), vertl.end()), vertl.end());
std::sort(vertr.begin(), vertr.end());
vertr.erase(std::unique(vertr.begin(), vertr.end()), vertr.end());
for (auto &[x, y] : edges) {
x = std::lower_bound(vertl.begin(), vertl.end(), x) - vertl.begin();
y = std::lower_bound(vertr.begin(), vertr.end(), y) - vertr.begin();
g[x].push_back(y);
}
bool repeat = true;
for (int i = 0; i < (int) vertl.size(); i++) {
l[i] = -1;
}
for (int i = 0; i < (int) vertr.size(); i++) {
r[i] = -1;
}
while (repeat) {
repeat = false;
for (int i = 0; i < (int) vertl.size(); i++) {
vis[i] = false;
}
for (int i = 0; i < (int) vertl.size(); i++) {
if (l[i] == -1 && cupleaza(i)) {
answer++;
repeat = true;
}
}
}
std::cout << answer;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |