#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
vector< vector<bool> >matriz;
void init(int R, int C, int sr, int sc, int M, char *S) {
matriz = vector< vector<bool> > (R,vector<bool>(C,true));
sr--;
sc--;
matriz[sr][sc]=0;
for(int i=0;i<M;i++){///marcando el camino de la serpiente
int dir=S[i];
if(dir=='N')sr--;
if(dir=='W')sc--;
if(dir=='S')sr++;
if(dir=='E')sc++;
matriz[sr][sc]=0;
}
}
int colour(int ar, int ac, int br, int bc) {
ar--;
ac--;
br--;
bc--;
vector< vector<bool> >visitados(matriz.size(),vector<bool> (matriz[0].size(),false));
int cont=0;
for(int i=ar;i<=br;i++){
for(int j=ac;j<=bc;j++){
if(matriz[i][j] && !visitados[i][j]){///si no esta pintado y podemos ir por ahí
visitados[i][j]=1;///lo pintamos
cont++;///nuevo color
queue< pair<int,int> >q;///cola donde almacenaremos los caminos
q.push(make_pair(i,j));///comenzaremos nuestro camino
while(!q.empty()){
int px=q.front().first,py=q.front().second,px1=px-1,py1=py,px2=px,py2=py-1,px3=px+1,py3=py,px4=px,py4=py+1;///designando nuevas direcciones a N,W,S,E
q.pop();
if(px1>=ar && px1<=br && py1>=ac && py1<=bc){///si es territorio dentro de la zona
if(matriz[px1][py1] && !visitados[px1][py1]){///si no esta pintado y podemos ir por ahí
visitados[px1][py1]=1;///lo pintamos
q.push(make_pair(px1,py1));///nuevo camino
}
}
if(px2>=ar && px2<=br && py2>=ac && py2<=bc){
if(matriz[px2][py2] && !visitados[px2][py2]){
visitados[px2][py2]=1;
q.push(make_pair(px2,py2));
}
}
if(px3>=ar && px3<=br && py3>=ac && py3<=bc){
if(matriz[px3][py3] && !visitados[px3][py3]){
visitados[px3][py3]=1;
q.push(make_pair(px3,py3));
}
}
if(px4>=ar && px4<=br && py4>=ac && py4<=bc){
if(matriz[px4][py4] && !visitados[px4][py4]){
visitados[px4][py4]=1;
q.push(make_pair(px4,py4));
}
}
}
}
}
}
return cont;
}
/*int main(){
int R,C,M,Q,sr,sc,ar,ac,br,bc;
string S;
cin>>R>>C>>M>>Q;
cin>>sr>>sc;
cin>>S;
init(R,C,sr,sc,M,S);
for(int i=0;i<Q;i++){
cin>>ar>>ac>>br>>bc;
int ans=colour(ar,ac,br,bc);
cout<<ans<<"\n";
}
return 0;
}*/
