이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
string a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector< vector<int> > adj;
int cnt = 0;
int vis[n][m];
memset(vis, -1, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 2; j++) {
if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') {
int cur = cnt;
adj.push_back(vector<int>());
cnt++;
if (i + 2 < n && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
int a = cnt;
if (~vis[i + 1][j]) {
a = vis[i + 1][j];
}
else {
adj.push_back(vector<int>());
vis[i][j] = vis[i + 1][j] = vis[i + 2][j] = cnt;
cnt++;
}
adj[cur].push_back(a);
adj[a].push_back(cur);
}
if (i + 1 < n && i && a[i + 1][j + 1] == 'W' && a[i - 1][j + 1] == 'R') {
int a = cnt;
if (~vis[i + 1][j + 1]) {
a = vis[i + 1][j + 1];
}
else {
adj.push_back(vector<int>());
vis[i - 1][j + 1] = vis[i + 1][j + 1] = vis[i][j + 1] = cnt;
cnt++;
}
adj[cur].push_back(a);
adj[a].push_back(cur);
}
if (i > 1 && a[i - 2][j + 2] == 'R' && a[i - 1][j + 2] == 'G') {
int a = cnt;
if (~vis[i - 2][j + 2]) {
a = vis[i - 2][j + 2];
}
else {
adj.push_back(vector<int>());
vis[i - 2][j + 2] = vis[i - 1][j + 2] = vis[i][j + 2] = cnt;
cnt++;
}
adj[cur].push_back(a);
adj[a].push_back(cur);
}
}
}
}
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << setw(5) << vis[i][j];
}
cout << "\n";
}*/
set< array<int, 2> > st;
st.insert({0, -1});
for (int i = 0; i < cnt; i++) {
auto it = --st.end();
if (adj[i].size() == 0) {
st.insert({(*it)[0] + 1, i});
}
for (auto &to: adj[i]) {
if ((*it)[1] == to) {
it--;
}
else {
st.insert({(*it)[0] + 1, i});
break;
}
}
while (st.size() > 4) {
st.erase(st.begin());
}
}
int res = (*(--st.end()))[0];
for (int j = 0; j < m; j++) {
for (int i = 0; i < n - 2; i++) {
if (!(~vis[i][j]) && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
res++;
}
}
}
cout << res << endl;
return 0;
}
/*
3 4
RGWR
GRGG
RGWW
4 4
RGWR
GRRG
WGGW
WWWR
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |