fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define FOR(i,a,b) for (int i=(int)a;i<=(int)b;i++)
  6. #define FORD(i,a,b) for (int i=(int)a;i>=(int)b;i--)
  7. #define fast_io ios::sync_with_stdio(0); cin.tie(0)
  8. #define pb push_back
  9. const int oo=1e9+7;
  10. const int maxn=1e6+5;
  11. int n,m,h;
  12. typedef pair<int,int> pii;
  13. vector <pii> b[maxn];
  14. vector <int> a[maxn],d[maxn],lowd(maxn);
  15. int dx[4]={0,1,0,-1};
  16. int dy[4]={1,0,-1,0};
  17. void BFS(int h1,int c1, int h2, int c2)
  18. {
  19.     //queue <pii> q;
  20.     pii q[maxn];
  21.     FOR(i,1,m)
  22.         FOR(j,1,n)
  23.             d[i][j]=oo;
  24.     int f=1,l=1,r=1;
  25.     //q.push({h1,c1});
  26.     d[h1][c1]=0;
  27.     lowd[f]=0;
  28.     q[l]={h1,c1};
  29.     while (l<=r)
  30.     {
  31.         int uh=q[l].first;
  32.         int uc=q[l].second;
  33.         l++;
  34.         if (uh==h2 && uc==c2) break;
  35.         FOR(i,0,3)
  36.         {
  37.             int vh=uh+dx[i];
  38.             int vc=uc+dy[i];
  39.             if (vh==0 || vh>m || vc==0 || vc>n) continue;
  40.             if (d[vh][vc]==oo)
  41.             {
  42.                 d[vh][vc]=d[uh][uc]+1;
  43.                 r++;
  44.                 q[r]={vh,vc};
  45.                 //q.push({vh,vc});
  46.                 lowd[r]=d[vh][vc];
  47.             }
  48.         }
  49.         while (f<=r && lowd[f]<=d[uh][uc]-2)
  50.         {
  51.             int x=q[f].first;
  52.             int y=q[f].second;
  53.             int gt=a[x][y];
  54.             f++;
  55.             for (auto v:b[gt])
  56.                 if (d[v.first][v.second]==oo)
  57.                 {
  58.                     d[v.first][v.second]=d[x][y]+3;
  59.                     r++;
  60.                     q[r]={v.first,v.second};
  61.                     //q.push({v.first,v.second});
  62.                     lowd[r]=d[v.first][v.second];
  63.                 }
  64.  
  65.         }
  66.         if (d[h2][c2]!=oo) break;
  67.     }
  68.     cout <<d[h2][c2]<<endl;
  69.  
  70. }
  71. signed main()
  72. {
  73.     //freopen ("COVID19.INP","r",stdin);
  74.     //freopen ("COVID19.OUT","w",stdout);
  75.     fast_io;
  76.     cin >>m>>n>>h;
  77.     FOR(i,1,m)
  78.     {
  79.         a[i].resize(n+5);
  80.         d[i].resize(n+5);
  81.         FOR(j,1,n)
  82.             cin >>a[i][j];
  83.     }
  84.     FOR(i,1,m)
  85.         FOR(j,1,n)
  86.             b[i*j].pb(pii(i,j));
  87.     FOR(i,1,h)
  88.     {
  89.         int h1,c1,h2,c2;
  90.         cin >>h1>>c1>>h2>>c2;
  91.         BFS(h1,c1,h2,c2);
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.03s 81100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/URjn9d
language:
C++14 (clang 8.0)
created:
13 days ago
visibility:
public

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!