#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector < vector < bool > > a;
vector < vector < bool > > visited;
int X1, Y1, X2, Y2;
void init(int N, int M, int sr, int sc, int len, char *s)
{
n = N;
m = M;
a.resize(n + 1);
visited.resize(n + 1);
for(int i = 0; i <= n; i++)
{
a[i].resize(m + 1, 0);
visited[i].resize(m + 1, 0);
}
int posx = sr;
int posy = sc;
a[posx][posy] = true;
for(int i = 0; i < len; i++)
{
if(s[i] == 'N')
posx--;
else if(s[i] == 'S')
posx++;
else if(s[i] == 'W')
posy--;
else
posy++;
//cout << posx << " " << posy << endl;
a[posx][posy] = true;
}
}
bool check(int x, int y)
{
return X1 <= x && x <= X2 && Y1 <= y && y <= Y2 && !visited[x][y] && !a[x][y];
}
void dfs(int x, int y)
{
//cout << "Tuka sum : " << x << " - " << y << endl;
visited[x][y] = true;
for(int dx = -1; dx <= 1; dx++)
{
for(int dy = -1; dy <= 1; dy++)
{
if(abs(dx) == abs(dy))
continue;
int nbx = x + dx;
int nby = y + dy;
if(check(nbx, nby))
dfs(nbx, nby);
}
}
}
int colour(int x1, int y1, int x2, int y2)
{
X1 = x1;
Y1 = y1;
X2 = x2;
Y2 = y2;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
visited[i][j] = false;
}
}
int ans = 0;
for(int i = X1; i <= X2; i++)
{
for(int j = Y1; j <= Y2; j++)
{
if(check(i, j))
{
dfs(i, j);
ans++;
}
}
}
return ans;
}
