#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 50;
int n, m, k;
int sx, sy;
string s;
bool bad[N][N];
int p[N*N];
int sz[N*N];
int was[N*N];
int get(int u) {
return (p[u] == u ? u : p[u] = get(p[u]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v)
return;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
void markBads() {
int x = sx, y = sy;
bad[sx][sy] = true;
for (char c : s) {
if (c == 'N')
x--;
if (c == 'S')
x++;
if (c == 'W')
y--;
if (c == 'E')
y++;
bad[x][y] = true;
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
sr--;
sc--;
sx = sr;
sy = sc;
s.clear();
for (int i = 0; i < M; i++)
s += S[i];
markBads();
}
int colour(int ar, int ac, int br, int bc) {
ar--;
ac--;
br--;
bc--;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p[i*m+j] = i*m+j;
sz[i*m+j] = 1;
}
}
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (j+1 <= bc && !bad[i][j] && !bad[i][j+1])
unite(i*m+j, i*m+j+1);
if (i+1 <= br && !bad[i][j] && !bad[i+1][j])
unite(i*m+j, (i+1)*m+j);
}
}
int ans = 0;
fill(was, was+n*m, false);
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (bad[i][j])
continue;
ans += !was[get(i*m+j)];
was[get(i*m+j)] = true;
}
}
return ans;
}
