#include "rainbow.h"
#define N 1000
#define M 1000
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int vv[N][M], ee1[N][M], ee2[N][M], ff[N][M], imin, imax, jmin, jmax;
void init(int n, int m, int i_, int j_, int l, char *dd) {
int h, i, j;
i_--, j_--;
if (n > 1000 || m > 1000) /* :( */
return;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
vv[i][j] = 1;
imin = imax = i_, jmin = jmax = j_;
vv[i_][j_] = 0;
for (h = 0; h < l; h++) {
if (dd[h] == 'N')
i_--;
else if (dd[h] == 'S')
i_++;
else if (dd[h] == 'W')
j_--;
else
j_++;
imin = min(imin, i_), imax = max(imax, i_);
jmin = min(jmin, j_), jmax = max(jmax, j_);
vv[i_][j_] = 0;
}
for (i = 0; i < n; i++)
for (j = 1; j < m; j++)
ee1[i][j] = vv[i][j] && vv[i][j - 1];
for (i = 1; i < n; i++)
for (j = 0; j < m; j++)
ee2[i][j] = vv[i][j] && vv[i - 1][j];
for (i = 1; i < n; i++)
for (j = 1; j < m; j++)
ff[i][j] = vv[i][j] && vv[i][j - 1] && vv[i - 1][j] && vv[i - 1][j - 1];
for (i = 0; i < n; i++)
for (j = 1; j < m; j++)
vv[i][j] += vv[i][j - 1];
for (j = 0; j < m; j++)
for (i = 1; i < n; i++)
vv[i][j] += vv[i - 1][j];
for (i = 0; i < n; i++)
for (j = 1; j < m; j++)
ee1[i][j] += ee1[i][j - 1];
for (j = 0; j < m; j++)
for (i = 1; i < n; i++)
ee1[i][j] += ee1[i - 1][j];
for (i = 0; i < n; i++)
for (j = 1; j < m; j++)
ee2[i][j] += ee2[i][j - 1];
for (j = 0; j < m; j++)
for (i = 1; i < n; i++)
ee2[i][j] += ee2[i - 1][j];
for (i = 0; i < n; i++)
for (j = 1; j < m; j++)
ff[i][j] += ff[i][j - 1];
for (j = 0; j < m; j++)
for (i = 1; i < n; i++)
ff[i][j] += ff[i - 1][j];
}
int rect(int aa[][M], int i1, int j1, int i2, int j2) {
return i1 > i2 || j1 > j2 ? 0 : aa[i2][j2] - (j1 == 0 ? 0 : aa[i2][j1 - 1]) - (i1 == 0 ? 0 : aa[i1 - 1][j2]) + (i1 == 0 || j1 == 0 ? 0 : aa[i1 - 1][j1 - 1]);
}
int colour(int i1, int j1, int i2, int j2) {
int v, e, f;
i1--, j1--, i2--, j2--;
v = rect(vv, i1, j1, i2, j2);
e = rect(ee1, i1, j1 + 1, i2, j2) + rect(ee2, i1 + 1, j1, i2, j2);
f = rect(ff, i1 + 1, j1 + 1, i2, j2);
if (i1 < imin && imax < i2 && j1 < jmin && jmax < j2)
f++;
return v - e + f;
}
