#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
bool used[55][55];
void init(int R, int C, int sr, int sc, int M, char *S) {
string T=string(S);
used[sr][sc]=true;
for(char c:T){
if(c=='N')sr--;
else if(c=='S')sr++;
else if(c=='W')sc--;
else sc++;
used[sr][sc]=true;
}
}
bool memo[55][55];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void dfs(int x,int y,int ar,int ac,int br,int bc){
memo[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<ar||nx>br||ny<ac||ny>bc||used[nx][ny])continue;
if(!memo[nx][ny])dfs(nx,ny,ar,ac,br,bc);
}
}
int colour(int ar, int ac, int br, int bc) {
int ans=0;
memset(memo,0,sizeof(memo));
for(int i=ar;i<=br;i++){
for(int j=ac;j<=bc;j++){
if(!memo[i][j]&&!used[i][j]){
ans++;
dfs(i,j,ar,ac,br,bc);
}
}
}
return ans;
}
