#include "rainbow.h"
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
using pii = pair<int, int>;
vector<vector<bool>> g;
vector<vector<int>> vst;
int n, m;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C;
g.resize(n + 2, vector<bool>(m + 2));
for(int i = 1; i <= m; i++){
g[0][i] = g[n + 1][i] = true;
}
for(int i = 1; i <= n; i++){
g[i][0] = g[i][m + 1] = true;
}
g[sr][sc] = true;
for(int i = 0; i < M; i++){
if(S[i] == 'N') sr--;
else if(S[i] == 'S') sr++;
else if(S[i] == 'W') sc--;
else sc++;
g[sr][sc] = true;
}
//for(int i = 0; i <= n + 1; i++) printv(g[i], cerr);
}
vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
void bfs(int sx, int sy, int ar, int ac, int br, int bc){
queue<pii> q;
q.push(mp(sx, sy));
vst[sx][sy] = true;
while(!q.empty()){
int x = q.front().F, y = q.front().S;
q.pop();
for(pii d : dir){
int nx = x + d.F, ny = y + d.S;
if(g[nx][ny] || vst[nx][ny]) continue;
if(nx < ar || br < nx || ny < ac || bc < ny) continue;
vst[nx][ny] = true;
q.push(mp(nx, ny));
}
}
}
int colour(int ar, int ac, int br, int bc) {
vst.clear();
vst.resize(n + 2, vector<int>(m + 2));
int ans = 0;
for(int i = ar; i <= br; i++){
for(int j = ac; j <= bc; j++){
if(g[i][j] || vst[i][j]) continue;
ans++;
bfs(i, j, ar, ac, br, bc);
}
}
return ans;
}
