fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. template <typename T>
  7. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<ll,ll> pl;
  11. typedef pair<int,int> pii;
  12.  
  13. #define gll(x) scanf("%lld",&x)
  14. #define gll2(x,y) scanf("%lld%lld",&x,&y)
  15. #define gll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&y)
  16. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  17. #define sz(x) ((int)x.size())
  18. #define s(x) sort(x.begin(),x.end())
  19. #define all(v) v.begin(),v.end()
  20. #define rs(v) { s(v) ; r(v) ; }
  21. #define r(v) {reverse(all(v));}
  22. #define pb push_back
  23. #define mp make_pair
  24. #define F first
  25. #define S second
  26. #define f(i,n) for(int i=0;i<n;i++)
  27. #define fr(i,n) for(int i=n-1;i>=0;i--)
  28. #define rep(i,a,b) for(int i=a;i<=b;i++)
  29. #define repr(i,a,b) for(int i=a;i>=b;i--)
  30.  
  31. const ll mod = 1000000007;
  32. const ll inf = (ll)5e16;
  33. const ld eps = 1e-12;
  34. const ll N = 10000005;
  35. const ll LOGN = 19;
  36. const ld PI = 3.14159265358979323846;
  37. ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  38. ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  39. ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  40.  
  41. int n,m,k;
  42. bool check(int i,int j)
  43. {
  44.     return(i>=0 && i<n && j>=0 && j<m );
  45. }
  46.  
  47. /*void bfs(int x1,int y1,int x2,int y2)
  48. {
  49.     queue<pii> Q;
  50.     Q.push({x1,y1});
  51.     sec[x1][y1]=0;
  52.     while(!Q.empty())
  53.     {
  54.         pii p=Q.front();
  55.         Q.pop();
  56.         int x=p.F;
  57.         int y=p.S;
  58.         rep(i,1,k)
  59.         {
  60.             if(!check(x,y+i))
  61.                  break;
  62.             if(sec[x][y]>=sec[x][y+i])
  63.                  break;
  64.             else 
  65.             {
  66.                 //cout<<"NOOO";
  67.                 sec[x][y+i]=sec[x][y]+1;
  68.                 Q.push({x,y+i});
  69.             }
  70.         }
  71.         rep(i,1,k)
  72.         {
  73.             if(!check(x,y-i))
  74.                 break;
  75.             if(sec[x][y]>=sec[x][y-i])
  76.                  break;
  77.             else 
  78.             {
  79.                 sec[x][y-i]=sec[x][y]+1;
  80.                 Q.push({x,y-i});
  81.             }
  82.         }
  83.         rep(i,1,k)
  84.         {
  85.             if(!check(x+i,y))
  86.                 break;
  87.             if(sec[x][y]>=sec[x+i][y])
  88.                  break;
  89.             else 
  90.             {
  91.                 sec[x+i][y]=sec[x][y]+1;
  92.                 Q.push({x+i,y});
  93.             }
  94.         }
  95.         rep(i,1,k)
  96.         {
  97.             if(!check(x-i,y))
  98.                 break;
  99.             if(sec[x][y]>=sec[x-i][y])
  100.                  break;
  101.             else 
  102.             {
  103.                 sec[x-i][y]=sec[x][y]+1;
  104.                 Q.push({x-i,y});
  105.             }
  106.         }
  107.     }
  108. }*/
  109.  
  110. int main()
  111. {
  112.     ios_base::sync_with_stdio(false);
  113.     cin.tie(NULL);
  114.     cin>>n>>m>>k;
  115.     //int n,m,k;
  116.     bool a[n][m];
  117.     int sec[n][m];
  118.     char c;
  119.     string s;
  120.     //memset(a,false,sizeof(a));
  121.     f(i,n)
  122.     {
  123.         f(j,m)
  124.             sec[i][j]=(int)1e5;
  125.     }
  126.     f(i,n)
  127.     {
  128.         //cin>>s;
  129.         f(j,m)
  130.         {
  131.  
  132.             cin>>c;
  133.             if(c=='.')
  134.                 a[i][j]=true;
  135.             else 
  136.                 a[i][j]=false;
  137.         }
  138.     }
  139.     int x1,y1,x2,y2;
  140.     cin>>x1>>y1>>x2>>y2;
  141.     x1--,y1--,x2--,y2--;
  142.     queue<pii> Q;
  143.     Q.push({x1,y1});
  144.     sec[x1][y1]=0;
  145.     pii p;int x,y;
  146.     while(!Q.empty())
  147.     {
  148.          p=Q.front();
  149.         Q.pop();
  150.          x=p.F;
  151.          y=p.S;
  152.         rep(i,1,k)
  153.         {
  154.             if(!check(x,y+i) || !a[x][y+i])
  155.                  break;
  156.             if(sec[x][y]>=sec[x][y+i])
  157.                  break;
  158.             if(sec[x][y+i]!=(int)1e5 && sec[x][y+i]>sec[x][y])
  159.             	continue;
  160.             else 
  161.             {
  162.                 //cout<<"NOOO";
  163.                 sec[x][y+i]=sec[x][y]+1;
  164.                 Q.push({x,y+i});
  165.             }
  166.         }
  167.         rep(i,1,k)
  168.         {
  169.             if(!check(x,y-i) || !a[x][y-i])
  170.                 break;
  171.             if(sec[x][y]>=sec[x][y-i])
  172.                  break;
  173.             if(sec[x][y-i]!=(int)1e5 && sec[x][y-i]>sec[x][y])
  174.             	continue;
  175.             else 
  176.             {
  177.                 sec[x][y-i]=sec[x][y]+1;
  178.                 Q.push({x,y-i});
  179.             }
  180.         }
  181.         rep(i,1,k)
  182.         {
  183.             if(!check(x+i,y) || !a[x+i][y])
  184.                 break;
  185.             if(sec[x][y]>=sec[x+i][y])
  186.                  break;
  187.         	if(sec[x+i][y]!=(int)1e5 && sec[x+i][y]>sec[x][y])
  188.             	continue;
  189.             else 
  190.             {
  191.                 sec[x+i][y]=sec[x][y]+1;
  192.                 Q.push({x+i,y});
  193.             }
  194.         }
  195.         rep(i,1,k)
  196.         {
  197.             if(!check(x-i,y) || !a[x-i][y])
  198.                 break;
  199.             if(sec[x][y]>=sec[x-i][y])
  200.                  break;
  201.             if(sec[x-i][y]!=(int)1e5 && sec[x-i][y]>sec[x][y])
  202.             	continue;
  203.             else 
  204.             {
  205.                 sec[x-i][y]=sec[x][y]+1;
  206.                 Q.push({x-i,y});
  207.             }
  208.         }
  209.     }
  210.  
  211.     if(sec[x2][y2]==(int)1e5)
  212.         cout<<"-1\n";
  213.     else cout<<sec[x2][y2];
  214.     return 0;
  215. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
3 4 4
....
###.
....
1 1 3 1
stdout
copy 
3
https://ideone.com/vB3Iqu
language:
C++14 (gcc 8.3)
created:
6 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!