#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define all(aaa) aaa.begin(), aaa.end()
string dir = "NSEW";
const int dx[4] = {-1, 1, 0, 0},
dy[4] = {0, 0, 1, -1};
const int N = 52, INF = 1e9;
int a[N][N];
int r, c;
int mnx, mny, mxx, mxy;
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
a[sr][sc] = 1;
mnx = sr;
mxx = sr;
mny = sc;
mxy = sc;
int x = sr, y = sc;
for (int i = 0; i < M; i++) {
int k = find(all(dir), S[i]) - dir.begin();
x += dx[k];
y += dy[k];
a[x][y] = 1;
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
}
}
int colour(int ar, int ac, int br, int bc) {
int ans = 1;
if (ar < mnx && mxx < br &&
ac < mny && mxy < bc) {
ans++;
}
// count of edges
for (int i = ar; i < br; i++) {
for (int j = ac; j <= bc; j++) {
ans += (a[i][j] || a[i + 1][j]);
}
}
for (int i = ar; i <= br; i++) {
for (int j = ac; j < bc; j++) {
ans += (a[i][j + 1] || a[i][j]);
}
}
// count of vertices
for (int i = ar; i < br; i++) {
for (int j = ac; j < bc; j++) {
if (a[i][j] || a[i + 1][j]
|| a[i][j + 1] || a[i + 1][j + 1])
ans--;
}
}
// count of useless
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
ans -= a[i][j];
}
}
return ans;
}
