#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
bool riv[N][N];
int component[N][N];
int R, C;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, 1, -1};
int component_id = 0;
bool in_bounds(int r, int c) {
return r >= 1 && r <= R && c >= 1 && c <= C;
}
void bfs(int sr, int sc) {
queue<pair<int, int>> q;
q.push({sr, sc});
component[sr][sc] = component_id;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (in_bounds(nr, nc) && !riv[nr][nc] && component[nr][nc] == -1) {
component[nr][nc] = component_id;
q.push({nr, nc});
}
}
}
}
void init(int r, int c, int sr, int sc, int m, char* s) {
R = r;
C = c;
memset(riv, 0, sizeof(riv));
memset(component, -1, sizeof(component));
component_id = 0;
int x = sr, y = sc;
riv[x][y] = true;
for (int i = 0; i < m; ++i) {
if (s[i] == 'N') --x;
else if (s[i] == 'S') ++x;
else if (s[i] == 'E') ++y;
else if (s[i] == 'W') --y;
riv[x][y] = true;
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (!riv[i][j] && component[i][j] == -1) {
bfs(i, j);
component_id++;
}
}
}
}
int colour(int r1, int c1, int r2, int c2) {
unordered_set<int> unique_components;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= c2; ++j) {
int id = component[i][j];
if (id != -1) {
unique_components.insert(id);
}
}
}
return unique_components.size();
}
