#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 55;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int R, C;
bitset<MAX> land[MAX];
void init(int _R, int _C, int sr, int sc, int M, char *S) {
R = _R; C = _C;
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
land[r][c] = true;
land[sr][sc] = false;
for (int i = 0; i < M; i++) {
int d = 0;
switch(S[i]) {
case 'N': d = 0; break;
case 'E': d = 1; break;
case 'S': d = 2; break;
case 'W': d = 3; break;
}
sr += dr[d];
sc += dc[d];
land[sr][sc] = false;
}
}
int color[MAX][MAX], _color = 0;
void dfs_1(int r, int c, int ar, int ac, int br, int bc) {
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (r >= ar && r <= br && c >= ac && c <= bc && land[nr][nc] && color[nr][nc] == 0) {
color[nr][nc] = color[r][c];
dfs_1(nr, nc, ar, ac, br, bc);
}
}
}
int colour(int ar, int ac, int br, int bc) {
for (int r = ar; r <= br; r++)
for (int c = ac; c <= bc; c++)
color[r][c] = 0;
_color= 0;
for (int r = ar; r <= br; r++) {
for (int c = ac; c <= bc; c++) {
if (land[r][c] && color[r][c] == 0) {
color[r][c] = ++_color;
dfs_1(r, c, ar, ac, br, bc);
}
}
}
return _color;
}
