#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T>
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 3005;
char w[MAX_N][MAX_N];
int n, m, a, b, id[MAX_N][MAX_N];
bool valid (char a, char b, char c) { return a == 'R' && b == 'G' && c == 'W'; }
vector<vector<int>> edge;
vector<int> ma;
bool dfs(int x) {
for (int u : edge[x]) if (~ma[u] || dfs(ma[u])) {
return ma[u] = x, ma[x] = u, true;
}
return false;
}
int max_clique(vector<pair<int,int>> alle) {
b += a;
edge.resize(b + 1);
ma.resize(b + 1, -1);
edge.resize(a + 1);
for (auto [x, y] : alle)
edge[x].pb(y + b);
int res = b;
for (int i = 1;i <= a;++i)
if (~ma[i] && dfs(i))
--res;
return res;
}
int solve() {
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j) {
if (valid(w[i][j-1], w[i][j], w[i][j+1]))
id[i][j] = ++b;
}
vector<pair<int,int>> alle;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j) {
if (valid(w[i-1][j], w[i][j], w[i+1][j])) {
++a;
if (id[i-1][j+1])
alle.pb(a, id[i-1][j+1]);
if (id[i][j])
alle.pb(a, id[i][j]);
if (id[i+1][j-1])
alle.pb(a, id[i+1][j-1]);
}
}
for (auto &[x, y] : alle)
y += a;
return max_clique(alle);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;++i)
cin >> w[i] + 1;
cout << solve() << '\n';
}
Compilation message
dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | cin >> w[i] + 1;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
