# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
252878 | 2020-07-26T11:44:31 Z | Sugardorj | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KB |
#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; } }