#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define eb emplace_back
vector<ii> cells, nodes, horiz, vert;
void init(int R, int C, int sr, int sc, int M, char *S) {
cells.eb(sr, sc);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') {
sr--;
} else if (S[i] == 'S') {
sr++;
} else if (S[i] == 'E') {
sc++;
} else {
sc--;
}
cells.eb(sr, sc);
}
sort(cells.begin(), cells.end());
cells.erase(unique(cells.begin(), cells.end()), cells.end());
for (const auto &[r, c] : cells) {
nodes.eb(r, c);
nodes.eb(r + 1, c);
nodes.eb(r, c + 1);
nodes.eb(r + 1, c + 1);
horiz.eb(r, c);
horiz.eb(r + 1, c);
vert.eb(r, c);
vert.eb(r, c + 1);
}
for (auto *vec : {&nodes, &horiz, &vert}) {
sort(vec->begin(), vec->end());
vec->erase(unique(vec->begin(), vec->end()), vec->end());
}
}
int colour(int ar, int ac, int br, int bc) {
int V = (br - ar + 1) * 2 + (bc - ac + 1) * 2 - 4, E = V;
bool border = 0;
for (const auto &[r, c] : nodes) {
if (ar + 1 <= r && r <= br && ac + 1 <= c && c <= bc) {
V++;
} else if (((ar == r || br + 1 == r) && (ac <= c && c <= bc + 1)) || ((ac == c || bc + 1 == c) && (ar <= r && r <= br + 1))) {
border = 1;
}
}
if (!border) {
bool wraps = 0;
for (const auto &[r, c] : cells) {
if (ar <= r && r <= br && ac <= c && c <= bc) {
wraps = 1;
}
}
if (!wraps) {
return 1;
}
V = nodes.size();
E = horiz.size() + vert.size();
int F = 2 - (V - E), water_F = cells.size();
return F - water_F;
}
for (const auto &[r, c] : horiz) {
if (ar + 1 <= r && r <= br && ac <= c && c <= bc) {
E++;
}
}
for (const auto &[r, c] : vert) {
if (ar <= r && r <= br && ac + 1 <= c && c <= bc) {
E++;
}
}
int F = 2 - (V - E), water_F = 0;
for (const auto &[r, c] : cells) {
if (ar <= r && r <= br && ac <= c && c <= bc) {
water_F++;
}
}
return F - water_F - 1;
}
