#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
int n;
vector<int> lab;
int cc;
void init(int _n){
n=_n;
cc=n;
lab.assign(n+1, -1);
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
void union_sets(int u, int v){
u=find_set(u), v=find_set(v);
if (u!=v){
if (lab[u]>lab[v]) swap(u, v);
lab[u]+=lab[v];
lab[v]=u;
--cc;
}
}
} dsu;
const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
bool a[100][100];
int r, c;
void init(int R, int C, int sr, int sc, int M, char *S) {
r=R, c=C;
a[sr][sc]=1;
for (int i=0; i<M; ++i){
if (S[i]=='N') --sr;
if (S[i]=='S') ++sr;
if (S[i]=='E') ++sc;
if (S[i]=='W') --sc;
a[sr][sc]=1;
}
}
int colour(int ar, int ac, int br, int bc) {
dsu.init((br-ar+1)*(bc-ac+1));
for (int i=ar; i<=br; ++i) for (int j=ac; j<=bc; ++j){
if (a[i][j]) --dsu.cc;
else{
for (int k=0; k<4; ++k){
int x=i+dx[k], y=j+dy[k];
if (x<ar || y<ac || x>br || y>bc || a[x][y]) continue;
dsu.union_sets((i-ar)*(bc-ac+1)+(j-ac), (x-ar)*(bc-ac+1)+(y-ac));
}
}
}
return dsu.cc;
}
