#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/
using namespace std;
typedef long long ll;
typedef long double ld;
//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr
const int N = 3007;
short f[N][N];
bool usedl[N * N], usedr[N * N];
int g[3][N * N], sz[N * N], used[N * N], mtr[N * N], mtl[N * N];
bool kun(int v, int c) {
used[v] = c;
for (int i = 0; i < sz[v]; ++i) {
int u = g[i][v];
if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
mtr[u] = v;
return true;
}
}
return false;
}
void dfs(int v) {
if (v == -1 || usedl[v])
return;
usedl[v] = 1;
for (int i = 0; i < sz[v]; ++i) {
int u = g[i][v];
if (mtl[v] == u)
continue;
if (!usedr[u]) {
usedr[u] = 1;
dfs(mtr[u]);
}
}
}
void solve() {
loop(i, N * N)
mtr[i] = mtl[i] = -1;
int n, m;
cin >> n >> m;
for (int i = 2; i <= n + 1; ++i) {
for (int j = 2; j <= m + 1; ++j) {
char c; cin >> c;
f[i][j] = (c == 'R' ? 1 : (c == 'G' ? 2 : 3));
}
}
for (int i = 2; i <= n + 1; ++i) {
for (int j = 2; j <= m + 1; ++j) {
if (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3) {
int v = (i - 2) * m + (j - 2);
if (f[i + 1][j] == 2 && f[i + 2][j] == 3)
g[sz[v]++][i] = (i - 2) * m + (j - 2);
if (f[i - 1][j + 1] == 1 && f[i + 1][j + 1] == 3)
g[sz[v]++][i] = (i - 3) * m + (j - 1);
if (f[i - 2][j + 2] == 1 && f[i - 1][j + 2] == 2)
g[sz[v]++][i] = (i - 4) * m + j;
}
}
}
int cnt = 0;
for (int i = 2; i <= n + 1; ++i)
for (int j = 2; j <= m + 1; ++j)
kun((i - 2) * m + (j - 2), ++cnt);
for (int i = 2; i <= n + 1; ++i)
for (int j = 2; j <= m + 1; ++j)
if (mtr[(i - 2) * m + (j - 2)] != -1)
mtl[mtr[(i - 2) * m + (j - 2)]] = (i - 2) * m + (j - 2);
for (int i = 2; i <= n + 1; ++i)
for (int j = 2; j <= m + 1; ++j)
if (mtl[(i - 2) * m + (j - 2)] == -1)
dfs((i - 2) * m + (j - 2));
int ans = 0;
for (int i = 2; i <= n + 1; ++i)
for (int j = 2; j <= m + 1; ++j)
ans += (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3 && usedl[(i - 2) * m + (j - 2)]) + (f[i][j] == 1 && f[i + 1][j] == 2 && f[i + 2][j] == 3 && !usedr[(i - 2) * m + (j - 2)]);
cout << ans;
}
signed main() {
//freopen("b2.txt", "r", stdin);
//freopen("ans9.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//int t; cin >> t; loop(i, t)
solve();
return 0;
}
Compilation message
dango_maker.cpp: In function 'bool kun(int, int)':
dango_maker.cpp:62:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
62 | if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
71148 KB |
Output is correct |
2 |
Correct |
41 ms |
71148 KB |
Output is correct |
3 |
Correct |
45 ms |
71148 KB |
Output is correct |
4 |
Correct |
41 ms |
71168 KB |
Output is correct |
5 |
Correct |
43 ms |
71288 KB |
Output is correct |
6 |
Incorrect |
42 ms |
71168 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
71148 KB |
Output is correct |
2 |
Correct |
41 ms |
71148 KB |
Output is correct |
3 |
Correct |
45 ms |
71148 KB |
Output is correct |
4 |
Correct |
41 ms |
71168 KB |
Output is correct |
5 |
Correct |
43 ms |
71288 KB |
Output is correct |
6 |
Incorrect |
42 ms |
71168 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
71148 KB |
Output is correct |
2 |
Correct |
41 ms |
71148 KB |
Output is correct |
3 |
Correct |
45 ms |
71148 KB |
Output is correct |
4 |
Correct |
41 ms |
71168 KB |
Output is correct |
5 |
Correct |
43 ms |
71288 KB |
Output is correct |
6 |
Incorrect |
42 ms |
71168 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |