#include <bits/stdc++.h>
using namespace std;
#include "rainbow.h"
#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif
const int mxN = 1001;
bool river[mxN][mxN], visited[mxN][mxN];
// {{{ HASHMAP
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash {
const uint64_t C = (long long)(4e18 * acos(0)) | 71;
const uint32_t RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
size_t operator()(uint64_t x) const {
return __builtin_bswap64((x ^ RANDOM) * C);
}
};
// }}}
int R,C;
void init(int _R, int _C, int sr, int sc, int M, char *S) {
R = _R, C = _C;
memset(river,0,sizeof(river));
int y = sr, x = sc;
gp_hash_table<char, pair<int,int>> mp; // dy, dx;
// unordered_map<char,pair<int,int>> mp;
mp['N'] = {-1, 0};
mp['S'] = {1, 0};
mp['W'] = {0, -1};
mp['E'] = {0, 1};
river[y][x] = 1;
for(int i=0; i<M; i++){
y += mp[S[i]].first;
x += mp[S[i]].second;
river[y][x] = 1;
dbg(y,x);
}
}
const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};
void dfs(int y, int x, int ar, int ac, int br, int bc){
visited[y][x] = 1;
for(int i=0; i<4; i++){
int newy = y + dy[i];
int newx = x + dx[i];
if(newy >= ar && newx >= ac && newy <= br && newx <= bc && !river[newy][newx] && !visited[newy][newx]){
dfs(newy, newx, ar, ac, br, bc);
}
}
}
int colour(int ar, int ac, int br, int bc) {
memset(visited,0,sizeof(visited));
int ans = 0;
for(int y=ar; y<=br; y++){
for(int x=ac; x<=bc; x++){
if(!river[y][x] && !visited[y][x]){
dfs(y,x,ar,ac,br,bc);
ans++;
}
}
}
return ans;
}
