# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
945134 | TAhmed33 | 무지개나라 (APIO17_rainbow) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
bool ok[51][51];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int mny, mxy, mnx, mxx;
map <char, int> lk = {
{'E', 0},
{'N', 1},
{'W', 2},
{'S', 3}
};
int n, m;
void init (int N, int M, int x, int y, int z, char *s) {
n = N; m = M;
x--; y--;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ok[i][j] = 1;
ok[x][y] = 0;
mny = mxy = y; mnx = mxx = x;
for (int i = 0; i < z; i++) {
x += dx[lk[s[i]]]; y += dy[lk[s[i]]];
mny = min(mny, y);
mxy = max(mxy, y);
mnx = min(mnx, x);
mxx = max(mxx, x);
ok[x][y] = 0;
}
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << ok[i][j];
}
cout << '\n';
}*/
}
int colour (int ar, int ac, int br, int bc) {
ar--; br--; ac--; bc--;
if (ar > br) swap(ar, br);
if (ac > bc) swap(ac, bc);
//cout << ar << " " << ac << ": " << br << " " << bc << '\n';
int v = 0, e = 0, f = 0;
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (!ok[i][j]) continue;
v++;
}
}
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (!ok[i][j]) continue;
if (i < br) if (ok[i + 1][j]) e++;
if (j < bc) if (ok[i][j + 1]) e++;
if (i < br && j < bc) if (ok[i + 1][j] && ok[i][j + 1] && ok[i + 1][j + 1]) f++;
}
}
if (ar > mnx && br < mxx && ac > mny && bc < mxy) f++;
return v - e + f;
}
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}