#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<vector<bool>> riv;
map<char, pair<int, int>> dir;
void init(signed r, signed c, signed sr, signed sc, signed M, char *S) {
dir['N'] = {-1, 0};
dir['S'] = {1, 0};
dir['W'] = {0, -1};
dir['E'] = {0, 1};
R = r; C = c;
riv.assign(R, vector<bool>(C));
pair<int, int> pos = {sr-1, sc-1};
riv[pos.first][pos.second]=1;
for (int i=0;i<M;i++) {
pos.first += dir[S[i]].first;
pos.second += dir[S[i]].second;
riv[pos.first][pos.second]=1;
}
}
vector<vector<bool>> vis;
bool dfs(pair<int, int> v, int ar, int ac, int br, int bc) {
if (v.first < ar || v.first > br) return 0;
if (v.second < ac || v.second > bc) return 0;
if (vis[v.first][v.second]) return 0;
if (riv[v.first][v.second]) return 0;
vis[v.first][v.second] = 1;
for (auto i: dir) {
dfs({v.first+i.second.first, v.second + i.second.second}, ar, ac, br, bc);
}
return 1;
}
signed colour(signed ar, signed ac, signed br, signed bc) {
ar--;ac--;br--;bc--;
vis.assign(R, vector<bool>(C));
int res = 0;
for (int i = ar; i<=br; i++) {
for (int j = ac; j<=bc; j++) {
res += dfs({i, j}, ar, ac, br, bc);
}
}
return res;
}
