fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,q;
  4. // vector<pair<int,int>> a[1000007];
  5. int f[307][307];
  6. int a[307][307];
  7. pair<int,int> xp,di;
  8. int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
  9. void bfs(){
  10.     for (int i=1;i<=n;i++) {
  11.         for (int j=1;j<=m;j++) f[i][j]=1e9;
  12.     }
  13.     queue<pair<int,int>> q[3000];
  14.     f[xp.first][xp.second]=0;
  15.     q[0].push(xp);
  16.     for (int i=0;i<=(n+m)*3;i++) {
  17.         while (q[i].empty()==0) {
  18.             pair<int,int> ii=q[i].front();
  19.             q[i].pop();
  20.             int u=ii.first,v=ii.second;
  21.             for (int i=0;i<4;i++) {
  22.                 int x=u+dx[i],y=v+dy[i],val;
  23.                 if (x<=0||y<=0||x>n||y>m) continue;
  24.                 if (a[u][v]==(i+2)%4) val=3;
  25.                 else if (a[u][v]==i) val=1; else val=2;
  26.                 if (f[x][y]>f[u][v]+val) {
  27.                     f[x][y]=f[u][v]+val;
  28.                     q[f[x][y]].push({x,y});
  29.                 }
  30.             }
  31.         }
  32.     }
  33.     cout<<f[di.first][di.second]<<'\n';
  34. }
  35. string s;
  36. int main() 
  37. {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cin>>n>>m>>q;
  41.     for (int i=1;i<=n;i++) {
  42.         cin>>s;
  43.         for (int j=1;j<=m;j++) {
  44.             char ch=s[j-1];
  45.             if (ch=='N') {
  46.                 a[i][j]=2;
  47.             }
  48.             if (ch=='E'){
  49.                 a[i][j]=3;
  50.             }
  51.             if (ch=='W'){
  52.                 a[i][j]=1;
  53.             }
  54.             if (ch=='S') {
  55.                 a[i][j]=0;
  56.             }
  57.         }
  58.     }
  59.     while (q--) {
  60.         cin>>xp.first>>xp.second>>di.first>>di.second;
  61.         bfs();
  62.     }
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DMKICJ
language:
C++14 (gcc 8.3)
created:
4 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!