#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
bool isRiver[N][N], vis[N][N];
char direction[4] = {'N', 'S', 'E', 'W'};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void init(int R, int C, int sr, int sc, int M, char *S) {
for(int i = 1; i <= R; i++) {
for(int j = 1; j <= C; j++) {
isRiver[i][j] = false;
}
}
isRiver[sr][sc] = true;
for(int i = 0; i < M; i++) {
for(int j = 0; j < 4; j++) {
if(direction[j] == S[i]) {
sr += dx[j];
sc += dy[j];
isRiver[sr][sc] = true;
break;
}
}
}
/*for(int i = 1; i <= R; i++) {
for(int j = 1; j <= C; j++) {
cout << isRiver[i][j] << " ";
}
cout << "\n";
}*/
}
void DoBfs(int row_min, int col_min, int row_max, int col_max, int cur_row, int cur_col) {
queue<pair<int, int> > bfs;
bfs.push({cur_row, cur_col});
vis[cur_row][cur_col] = true;
while(!bfs.empty()) {
cur_row = bfs.front().first, cur_col = bfs.front().second;
bfs.pop();
for(int i = 0; i < 4; i++) {
if(vis[cur_row + dx[i]][cur_col + dy[i]] || isRiver[cur_row + dx[i]][cur_col + dy[i]])
continue;
if(cur_row + dx[i] < row_min || cur_row + dx[i] > row_max)
continue;
if(cur_col + dy[i] < col_min || cur_col + dy[i] > col_max)
continue;
bfs.push({cur_row + dx[i], cur_col + dy[i]});
vis[cur_row + dx[i]][cur_col + dy[i]] = true;
}
}
}
int colour(int ar, int ac, int br, int bc) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
vis[i][j] = false;
}
}
int cnt = 0;
for(int i = ar; i <= br; i++) {
for(int j = ac; j <= bc; j++) {
if(!vis[i][j] && !isRiver[i][j]) {
DoBfs(ar, ac, br, bc, i, j);
cnt++;
}
}
}
return cnt;
}
