#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back
void ckmin(int& a, int b){
a = min(a, b);
}
void ckmax(int& a, int b){
a = max(a, b);
}
vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};
bool filled[55][55];
struct DSU{
vi e;
void init(int N){
e = vi(N, -1);
}
int get(int a){
if(e[a] < 0) return a;
e[a] = get(e[a]);
return e[a];
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return 0;
if(-e[a] < -e[b]) swap(a, b);
e[a]+=e[b];
e[b] = a;
return 1;
}
};
void init(int R, int C, int sr, int sc, int M, char *S) {
for(int i = 0; i <= M; i++){
filled[sr][sc] = 1;
if(i < M){
for(int d = 0; d < 4; d++){
if(S[i] == dchar[d]){
sr+=dx[d];
sc+=dy[d];
break;
}
}
}
}
}
int colour(int ar, int ac, int br, int bc) {
DSU dsu;
dsu.init(55*55);
for(int i = ar; i <= br; i++){
for(int j = ac; j <= bc; j++){
if(!filled[i][j]){
for(int d = 0; d < 4; d++){
int new_r = i+dx[d];
int new_c = j+dy[d];
if(ar <= new_r && new_r <= br && ac <= new_c && new_c <= bc && !filled[new_r][new_c]){
dsu.unite(55*i+j, 55*new_r+new_c);
}
}
}
}
}
int ans = 0;
for(int i = ar; i <= br; i++){
for(int j = ac; j <= bc; j++){
if(!filled[i][j]){
if(dsu.get(55*i+j) == 55*i+j){
ans++;
}
}
}
}
return ans;
}
