fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define sqr(x) (x)*(x)
  4. #define sz(a) int(a.size())
  5. #define reset(a,b) memset(a,b,sizeof(a))
  6. #define oo 1000000007
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<int,int> pii;
  11. typedef long long ll;
  12.  
  13.  
  14. const int maxn=5007;
  15.  
  16. int T;
  17. int V,H,VG[maxn],HG[maxn],K;
  18. int lN[maxn],lS[maxn],rN[maxn],rS[maxn],llN[maxn],llS[maxn];
  19. int tW[maxn],tE[maxn],bW[maxn],bE[maxn],bbW[maxn],bbE[maxn];
  20. char VD[maxn],HD[maxn];
  21.  
  22.  
  23.  
  24. struct DijkstraMachine{
  25.     int x1,y1,x2,y2;
  26.     vector<pii> Vline,Hline;
  27.     map<pii,int> id;
  28.     int d[222],N,start,finish;
  29.     vector<pii> e[222];
  30.     bool free1[222];
  31.  
  32.     void init(int a, int b, int c, int d){
  33.         x1=a; y1=b; x2=c; y2=d;
  34.         Vline.clear(); Hline.clear();
  35.     }
  36.  
  37.     void addVline(int i){
  38.         if(i==-1) return;
  39.         int dir;
  40.         if(VD[i]=='N') dir=1; else dir=-1;
  41.         Vline.pb(pii(VG[i],dir));
  42.  
  43.     }
  44.  
  45.     void addHline(int i){
  46.         if(i==-1) return;
  47.         int dir;
  48.         if(HD[i]=='E') dir=1; else dir=-1;
  49.         Hline.pb(pii(HG[i],dir));
  50.     }
  51.  
  52.     void addLineWithPoint(int x, int y){
  53.         int xi=lower_bound(VG+1,VG+V+1,x)-VG;
  54.         if(xi>V) xi=V;
  55.         int yi=lower_bound(HG+1,HG+H+1,y)-HG;
  56.         if(yi>H) yi=H;
  57.         addVline(llN[xi]);
  58.         addVline(llS[xi]);
  59.         addVline(lN[xi]);
  60.         addVline(lS[xi]);
  61.         addVline(rN[xi]);
  62.         addVline(rS[xi]);
  63.         addHline(bbE[yi]);
  64.         addHline(bbW[yi]);
  65.         addHline(tE[yi]);
  66.         addHline(tW[yi]);
  67.         addHline(bE[yi]);
  68.         addHline(bW[yi]);
  69.     }
  70.  
  71.     void normalize(){
  72.         sort(Vline.begin(),Vline.end());
  73.         Vline.resize(unique(Vline.begin(),Vline.end())-Vline.begin());
  74.         sort(Hline.begin(),Hline.end());
  75.         Hline.resize(unique(Hline.begin(),Hline.end())-Hline.begin());
  76.     }
  77.  
  78.     int getid(int x, int y){
  79.         int v=id[pii(x,y)];
  80.         if(v) return v;
  81.         id[pii(x,y)]=++N;
  82.         e[N].clear();
  83.         return N;
  84.     }
  85.  
  86.     int calc(){
  87.         //init the graph
  88.         id.clear(); N=0;
  89.         start=getid(x1,y1);
  90.         finish=getid(x2,y2);
  91.         for(int i=0; i<sz(Vline); ++i)
  92.             for(int j=0; j<sz(Hline); ++j){
  93.                 int xx=Vline[i].first, yy=Hline[j].first;
  94.                 int u=getid(xx,yy);
  95.  
  96.                 for(int i2=0; i2<sz(Vline); ++i2){
  97.                     int xx2=Vline[i2].first;
  98.                     int v=getid(xx2,yy);
  99.                     if(v==u) continue;
  100.                     if( (xx2 - xx) * Hline[j].second > 0 )
  101.                         e[u].pb(pii(v,abs(xx2-xx)));
  102.                 }
  103.  
  104.                 for(int j2=0; j2<sz(Hline); ++j2){
  105.                     int yy2=Hline[j2].first;
  106.                     int v=getid(xx,yy2);
  107.                     if(v==u) continue;
  108.                     if( (yy2 - yy) * Vline[i].second > 0 )
  109.                         e[u].pb(pii(v,abs(yy2-yy)));
  110.                 }
  111.  
  112.                 if(x1==xx && yy!=y1 && (yy-y1)*Vline[i].second>0)
  113.                     e[start].pb(pii(u,abs(yy-y1)));
  114.  
  115.                 if(x1!=xx && yy==y1 && (xx-x1)*Hline[j].second>0)
  116.                     e[start].pb(pii(u,abs(xx-x1)));
  117.  
  118.                 if(x2==xx && yy!=y2 && (y2-yy)*Vline[i].second>0)
  119.                     e[u].pb(pii(finish,abs(y2-yy)));
  120.  
  121.                 if(x2!=xx && yy==y2 && (x2-xx)*Hline[j].second>0)
  122.                     e[u].pb(pii(finish,abs(x2-xx)));
  123.  
  124.             }
  125.  
  126.         for(int i=0; i<sz(Vline); ++i)
  127.             if(x1 == x2 && x1==Vline[i].first && (y2-y1)*Vline[i].second>0)
  128.                 e[start].pb(pii(finish,abs(y2-y1)));
  129.         for(int j=0; j<sz(Hline); ++j)
  130.             if(y1 == y2 && y1==Hline[j].first && (x2-x1)*Hline[j].second>0)
  131.                 e[start].pb(pii(finish,abs(x2-x1)));
  132.  
  133.         // do dijktra
  134.         for(int u=1; u<=N; ++u) d[u]=oo, free1[u]=1;
  135.         d[start]=0;
  136.         while(1){
  137.             int u=-1, minv=oo;
  138.             for(int v=1; v<=N; ++v)
  139.                 if(free1[v] && minv>d[v]){
  140.                     minv=d[v];
  141.                     u=v;
  142.                 }
  143.             if(u==-1 || u==finish) break;
  144.             free1[u]=0;
  145.             for(int i=0; i<sz(e[u]); ++i){
  146.                 int v=e[u][i].first, w=e[u][i].second;
  147.                 if(free1[v] && d[v]>d[u]+w)
  148.                     d[v]=d[u]+w;
  149.             }
  150.         }
  151.         if(d[finish]==oo) d[finish]=-1;
  152.         return d[finish];
  153.     }
  154.  
  155. }dijk;
  156.  
  157. int main(){
  158.     //freopen("input.txt","r",stdin);
  159.     scanf("%d",&T);
  160.     for(int tt=1; tt<=T; ++tt){
  161.         scanf("%d%d%d",&V,&H,&K);
  162.         VG[1]=0;
  163.         int v;
  164.         for(int i=2; i<=V; ++i){
  165.             scanf("%d",&v);
  166.             VG[i]=VG[i-1]+v;
  167.         }
  168.         HG[1]=0;
  169.         for(int i=2; i<=H; ++i){
  170.             scanf("%d",&v);
  171.             HG[i]=HG[i-1]+v;
  172.         }
  173.         scanf("%s",VD+1); scanf("%s",HD+1);
  174.  
  175.         int pN=-1, pS=-1;
  176.         for(int i=1; i<=V; ++i){
  177.             llN[i]=pN; llS[i]=pS;
  178.             if(VD[i]=='N') pN=i;
  179.             else pS=i;
  180.             lN[i]=pN; lS[i]=pS;
  181.         }
  182.         pN=-1; pS=-1;
  183.         for(int i=V; i>=1; --i){
  184.             rN[i]=pN; rS[i]=pS;
  185.             if(VD[i]=='N') pN=i;
  186.             else pS=i;
  187.         }
  188.  
  189.         int pE=-1, pW=-1;
  190.         for(int i=1; i<=H; ++i){
  191.             bbW[i]=pW; bbE[i]=pE;
  192.             if(HD[i]=='E') pE=i;
  193.             else pW=i;
  194.             bW[i]=pW; bE[i]=pE;
  195.         }
  196.         pE=-1; pW=-1;
  197.         for(int i=H; i>=1; --i){
  198.             tW[i]=pW; tE[i]=pE;
  199.             if(HD[i]=='E') pE=i;
  200.             else pW=i;
  201.         }
  202.  
  203.         // solve
  204.  
  205.         int x1,y1,x2,y2;
  206.         for(int it=0; it<K; ++it){
  207.             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  208.             dijk.init(x1,y1,x2,y2);
  209.             dijk.addLineWithPoint(x1,y1);
  210.             dijk.addLineWithPoint(x2,y2);
  211.             dijk.normalize();
  212.             printf("%d\n",dijk.calc());
  213.         }
  214.     }
  215. }
Success #stdin #stdout 0s 3772KB
comments (?)
stdin
copy 
1
6 6 4
1 1 2 1 1
1 1 2 1 1
NNNSSS
WWWEEE
5 4 5 4
2 2 4 4
3 2 3 0
6 6 5 5
stdout
copy 
0
4
10
14
https://ideone.com/yYnzoF
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!