#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
set < pair < int, int > > nodes, ver_edges, hor_edges, river;
int min_x = inf, max_x = -inf, min_y = inf, max_y = -inf;
void add_node(int x, int y)
{
nodes.insert({x, y});
}
void add_hor_edge(int x, int y)
{
hor_edges.insert({x, y});
}
void add_ver_edge(int x, int y)
{
ver_edges.insert({x, y});
}
void add_river(int x, int y)
{
add_node(x, y);
add_node(x, y + 1);
add_node(x + 1, y);
add_node(x + 1, y + 1);
add_hor_edge(x, y);
add_hor_edge(x + 1, y);
add_ver_edge(x, y);
add_ver_edge(x, y + 1);
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
river.insert({x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
add_river(sr, sc);
for (int i = 0; i < M; i ++)
{
if (S[i] == 'N')
sr --;
else
if (S[i] == 'S')
sr ++;
else
if (S[i] == 'W')
sc --;
else
if (S[i] == 'E')
sc ++;
else assert(false);
add_river(sr, sc);
}
}
int query_nodes(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : nodes)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_hor_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : hor_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_ver_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : ver_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_river(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : river)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int colour(int ar, int ac, int br, int bc)
{
int V = query_nodes(ar + 1, ac + 1, br, bc) + (br - ar + 2) * 2 + (bc - ac) * 2;
int E = 0;
E = E + query_hor_edges(ar + 1, ac, br, bc) + (bc - ac + 1) * 2;
E = E + query_ver_edges(ar, ac + 1, br, bc) + (br - ar + 1) * 2;
int C = 1;
if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
C ++;
/// V + F = E + C + 1
/// F = E - V + C + 1
int F = E - V + C - query_river(ar, ac, br, bc);
///cout << "V " << V << " E " << E << " C " << C << endl;
return F;
}
