#include <iostream>
#include <queue>
#include "rainbow.h"
using namespace std;
bool B[55][55];
bool V[55][55];
int R,C;
int rmov[]={1,-1,0,0};
int cmov[]={0,0,1,-1};
queue<pair<int,int>> Q;
void init(int R_, int C_, int sr, int sc, int M, char *S) {
R=R_;
C=C_;
sr--;
sc--;
B[sr][sc]=true;
for(int i=0;i<M;i++){
if(S[i]=='S')
sr++;
if(S[i]=='N')
sr--;
if(S[i]=='E')
sc++;
if(S[i]=='W')
sc--;
B[sr][sc]=true;
}
/*
for(int i=0;i<R;i++){
for(int j=0;j<C;j++)
cout<<B[i][j];
cout<<endl;
}
*/
}
int colour(int ar, int ac, int br, int bc) {
ar--;
ac--;
br--;
bc--;
int ans=0;
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
V[i][j]=B[i][j];
for(int i=ar;i<=br;i++)
for(int j=ac;j<=bc;j++)
if(!V[i][j]){
ans++;
while(Q.size())
Q.pop();
Q.push({i,j});
while(Q.size()){
pair<int,int> p=Q.front();
V[p.first][p.second]=true;
Q.pop();
for(int m=0;m<4;m++)
if(!V[p.first+rmov[m]][p.second+cmov[m]] and ar<=p.first+rmov[m] and p.first+rmov[m]<=br and ac<=p.second+cmov[m] and p.second+cmov[m]<=bc)
Q.push({p.first+rmov[m],p.second+cmov[m]});
}
}
return ans;
}
