#include "rainbow.h"
#include <queue>
#include <vector>
#include <cassert>
using namespace std;
const vector<int> dx = { 0, 1, 0, -1 };
const vector<int> dy = { 1, 0, -1, 0 };
bool river[55][55], vis[55][55];
void init(int R, int C, int sr, int sc, int M, char *S) {
assert(R <= 50 && C <= 50);
--sr, --sc;
river[sr][sc] = true;
for(int i = 0; i < M; ++i) {
if(S[i] == 'N') --sr;
if(S[i] == 'S') ++sr;
if(S[i] == 'W') --sc;
if(S[i] == 'E') ++sc;
river[sr][sc] = true;
}
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
for(int i = ar; i < br; ++i) {
for(int j = ac; j < bc; ++j) {
vis[i][j] = false;
}
}
int ans = 0;
for(int i = ar; i < br; ++i) {
for(int j = ac; j < bc; ++j) {
if(vis[i][j] || river[i][j]) continue;
queue<pair<int, int> > que; que.push(make_pair(i, j));
vis[i][j] = true;
while(!que.empty()) {
pair<int, int> u = que.front(); que.pop();
for(int k = 0; k < 4; ++k) {
int tx = u.first + dx[k], ty = u.second + dy[k];
if(ar <= tx && tx < br && ac <= ty && ty < bc && !river[tx][ty] && !vis[tx][ty]) {
vis[tx][ty] = true;
que.push(make_pair(tx, ty));
}
}
}
++ans;
}
}
return ans;
}
