#include<bits/stdc++.h>
using namespace std;
const int N = (int)3e3+7;
const long long INF = (long long)1e18+7;
int n, m, mt[200], T;
char a[N][N];
int used[200];
vector<int> g[200];
int get(int i, int j) {
return (i-1)*m+j;
}
bool dfs(int v) {
if(used[v] == T) {
return 0;
}
used[v] = T;
for(auto to : g[v]) {
if(mt[to] == -1) {
mt[to] = v;
return 1;
}
}
for(auto to : g[v]) {
if(dfs(mt[to])) {
return 1;
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
mt[get(i, j)]=-1;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(j+2<=m) {
if(a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W') {
g[get(i, j)].push_back(get(i, j+2));
g[get(i, j+2)].push_back(get(i, j));
}
}
if(i+2<=n) {
if(a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W') {
g[get(i, j)].push_back(get(i+2, j));
g[get(i+2, j)].push_back(get(i, j));
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
T++;
if(dfs(get(i, j))) {
ans++;
}
}
}
cout << ans/2;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |