# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
252878 | Sugardorj | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 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;
long long b[323567],c[323456],a[323][456],tt,d[334564],e[456744];
long long x,m,n,t,k,l;
long long i , j,r,s,y,z;
string p;
queue<pair<long long,long long>> q,qq;
int main(){
cin >> n>>m>>l>>k>>x>>y>>p;
tt=1456785678;
a[x][y]=tt;
for (i = 0; i<l; i ++){
if (p[i]=='N')
x--;
if (p[i]=='S')
x++;
if (p[i]=='W')
y--;
if (p[i]=='E')
y++;
a[x][y]=tt;
}
for (i = 1; i <=k ; i ++){
cin >> x>>y>>l>>r;
s=0;
for (j = x; j<=l; j++){
for (z = y; z<=r;z++){
if (a[j][z]>= i){
continue;
}
s++;
q=qq;
q.push({j,z});
while(q.size()){
long long xx=q.front().first;
long long yy=q.front().second;
q.pop();
if (xx+1<=l&&a[xx+1][yy]<i){
q.push({xx+1,yy});
a[xx+1][yy]=i;
}
if (xx-1>=x&&a[xx-1][yy]<i){
a[xx-1][yy]=i;
q.push({xx-1,yy});}
if (yy+1<=r&&a[xx][yy+1]<i){
a[xx][yy+1]=i;
q.push({xx,yy+1});}
if (yy-1>=y&&a[xx][yy-1]<i){
a[xx][yy-1]=i;
q.push({xx,yy-1});}
}
}
}
cout <<s<<endl;
}
}