#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int a[50][200000];
bool v[50][200000];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void init(int R, int C, int sr, int sc, int M, char *S) {
sr--; sc--;
a[sr][sc] = 1;
for(int i = 0; i < M; i++) {
if(S[i] == 'N') sr--;
else if(S[i] == 'E') sc++;
else if(S[i] == 'S') sr++;
else if(S[i] == 'W') sc--;
a[sr][sc] = 1;
}
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0;
ar--; ac--; br--; bc--;
for(int i = ar; i <= br; i++) {
for(int j = ac; j <= bc; j++) if(a[i][j] == 0 && v[i][j] == 0) {
ans++;
queue<pair<int, int>> q;
q.push({i, j});
v[i][j] = 1;
while(!q.empty()) {
pair<int, int> c = q.front();
q.pop();
for(int k = 0; k < 4; k++) {
int nx = c.first+dx[k], ny = c.second+dy[k];
if(nx < ar || nx > br || ny < ac || ny > bc) continue;
if(a[nx][ny] == 1 || v[nx][ny] == 1) continue;
v[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
for(int i = ar; i <= br; i++) for(int j = ac; j <= bc; j++) v[i][j] = 0;
return ans;
}
