// moreflags=grader.cpp
// 6
// :(
#include "rainbow.h"
#include<set>
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<cassert>
namespace{
int R, C;
std::set<std::pair<int, int>> cells;
std::vector<std::vector<char>> have;
}
void init(int R_, int C_, int sr, int sc, int M, char *S) {
R=R_; C=C_;
cells.clear();
--sr;--sc;
cells.insert({sr, sc});
for(int i=0; i<M; ++i){
switch(S[i]){
case 'N': --sr; break;
case 'W': --sc; break;
case 'E': ++sc; break;
case 'S': ++sr; break;
default: assert(false); __builtin_unreachable();
}
cells.insert({sr, sc});
}
have.assign(R, std::vector<char>(C, 0));
for(auto [r, c]: cells) have[r][c]=1;
}
int colour(int ar, int ac, int br, int bc) {
--ar;--ac;
static std::vector<std::pair<int, int>> queue;
int front=0; queue.clear();
for(int r=ar; r<br; ++r)
for(int c=ac; c<bc; ++c)
assert(have[r][c]==0 or have[r][c]==1);
assert(ar<br); assert(ac<bc);
int result{};
for(int r=ar; r<br; ++r)
for(int c=ac; c<bc; ++c)
if(have[r][c]==0){
++result;
//std::array<int, 4> bounds{{r, c, r+1, c+1}};
front=(int)queue.size();
queue.push_back(std::make_pair(r, c));
have[r][c]=2;
while(front<(int)queue.size()){
auto [r, c]=queue[front++];
/*
bounds[0]=std::min(bounds[0], r);
bounds[1]=std::min(bounds[1], c);
bounds[2]=std::max(bounds[2], r+1);
bounds[3]=std::max(bounds[3], c+1);
*/
for(int _=0, a=1, b=0; _<4; ++_, std::swap(a, b), b=-b){
if(unsigned(r+a-ar)<unsigned(br-ar) and unsigned(c+b-ac)<unsigned(bc-ac) and
have[r+a][c+b]==0){
have[r+a][c+b]=2;
queue.push_back({r+a, c+b});
}
}
}
//regions
//blocks.push_back(bounds);
}
for(auto [r, c]: queue) {
assert(have[r][c]==2);
have[r][c]=0;
}
return result;
}
