#include <bits/stdc++.h>
using namespace std;
#include "rainbow.h"
set<pair<int, int>> relevantes;
set<pair<int, int>> agua;
int dx[] = {1,-1,0,0,1,-1,1,-1};
int dy[] = {0,0,1,-1,1,1,-1,-1};
void dfs(int x, int y, set<pair<int, int>> &marc, int ar, int ac, int br, int bc)
{
marc.emplace(x, y);
// cerr << x << " " << y << " ok " << '\n';
for (int k = 0; k < 4; k++)
{
int hx = x + dx[k], hy = y + dy[k];
if (hx < ar || hy < ac || hx > br || hy > bc) continue;
if (agua.count(make_pair(hx, hy)) || marc.count(make_pair(hx, hy))) continue;
dfs(hx, hy, marc, ar, ac, br, bc);
}
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
agua.emplace(sr, sc); relevantes.emplace(sr, sc);
for (int k = 0; k < 8; k++) relevantes.emplace(sr+dx[k], sc+dy[k]);
// cerr << "snake: " << '\n';
// cerr << "sr: " << sr << ", sc: " << sc << '\n';
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--;
agua.emplace(sr, sc); relevantes.emplace(sr, sc);
// cerr << "sr: " << sr << ", sc: " << sc << '\n';
for (int k = 0; k < 8; k++) relevantes.emplace(sr+dx[k], sc+dy[k]);
}
}
int colour(int ar, int ac, int br, int bc)
{
set<pair<int, int>> marc; int numAgua = 0; int resp = 0;
for (auto [x, y] : relevantes)
{
if (x < ar || y < ac || x > br || y > bc) continue;
if (agua.count(make_pair(x, y))) {numAgua++; continue;}
if (marc.count(make_pair(x, y))) continue;
dfs(x, y, marc, ar, ac, br, bc); resp++;
// cerr << "thats comp" << '\n';
}
// cerr << "numAgua: " << numAgua << '\n';
if (numAgua == 0) return 1;
return resp;
}
