#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (auto &x : a) cin >> x;
int ans = 0;
vector<vector<bool>> vis(n, vector<bool>(m));
const int dx[][2] = {{1, 2}, {-1, 1}, {-1, -2}};
const string match = "RGW";
auto in = [&](int x, int y) {
return x>=0 && y>=0 && x<n && y<m;
};
auto check = [&](int x, int y, queue<ar<int, 2>> &v) {
int idx = a[x][y] == 'R' ? 0 : a[x][y] == 'G' ? 1 : 2;
bool ok = 1;
for (int d = 0; d < 2; d++) {
int nx = x + dx[idx][d];
if (!in(nx, y) || a[nx][y] != match[idx + dx[idx][d]]) {
ok = 0;
break;
}
}
if (ok) {
if (!vis[x][y]) v.push({x, y}), vis[x][y] = 1;
for (int d = 0; d < 2; d++) {
int nx = x + dx[idx][d];
if (!vis[nx][y]) {
vis[nx][y] = 1;
v.push({nx, y});
}
}
}
bool ok2 = 1;
for (int d = 0; d < 2; d++) {
int ny = y + dx[idx][d];
if (!in(x, ny) || a[x][ny] != match[idx + dx[idx][d]]) {
ok2 = 0;
break;
}
}
if (ok2) {
if (!vis[x][y]) v.push({x, y}), vis[x][y] = 1;
for (int d = 0; d < 2; d++) {
int ny = y + dx[idx][d];
if (!vis[x][ny]) {
v.push({x, ny});
vis[x][ny] = 1;
}
}
}
};
vector<vector<int>> time(n, vector<int>(m));
int timer = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) if (!vis[i][j]) {
queue<ar<int, 2>> q;
check(i, j, q);
vector<ar<int, 2>> cur;
while (q.size()) {
auto [x, y] = q.front();
cur.push_back(q.front());
q.pop();
check(x, y, q);
}
auto check_right = [&](int x, int y) -> bool {
if (y + 2 >= m) return 0;
for (int d = 0; d < 3; d++) {
if (a[x][y+d] != match[d] || time[x][y+d] == timer) {
return 0;
}
}
return 1;
};
auto check_down = [&](int x, int y) -> bool {
if (x + 2 >= n) return 0;
for (int d = 0; d < 3; d++) {
if (a[x+d][y] != match[d] || time[x+d][y] == timer) {
return 0;
}
}
return 1;
};
if (cur.size()) {
// choose horizontal / vertical
sort(all(cur));
int cnt1 = 0, cnt2 = 0;
for (auto [x, y] : cur) {
if (check_right(x, y)) {
time[x][y] = time[x][y+1] = time[x][y+2] = timer;
cnt1++;
}
}
timer++;
for (auto [x, y] : cur) {
if (check_down(x, y)) {
time[x][y] = time[x+1][y] = time[x+2][y] = timer;
cnt2++;
}
}
timer++;
ans += max(cnt1, cnt2);
}
}
}
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 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 |
1 ms |
500 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
460 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 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 |
1 ms |
500 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
460 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
456 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
456 KB |
Output is correct |
27 |
Correct |
1 ms |
356 KB |
Output is correct |
28 |
Correct |
0 ms |
352 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
352 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
356 KB |
Output is correct |
33 |
Correct |
0 ms |
360 KB |
Output is correct |
34 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 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 |
1 ms |
500 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
460 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
456 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
456 KB |
Output is correct |
27 |
Correct |
1 ms |
356 KB |
Output is correct |
28 |
Correct |
0 ms |
352 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
352 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
356 KB |
Output is correct |
33 |
Correct |
0 ms |
360 KB |
Output is correct |
34 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |