fork(4) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <bits/stdc++.h>        //include every c++ library
  7.                                 //fgets(array_name,array_size,stdin);
  8.                                 //FLT_MAX FLT_MIN INT_MAX INT_MIN DBL_MAX DBL_MIN
  9. #define mod 1000000007
  10. #define ll long long int
  11. using namespace std;
  12.  
  13. struct point
  14. {
  15.      ll val;
  16.      ll X;
  17.      ll Y;
  18. };
  19.  
  20. bool operator<(point const& n1, point const& n2)
  21. {
  22.     return n1.val<n2.val;
  23. }
  24.  
  25. ll A[105][105],B[105][105];
  26.  
  27. /*void check(ll A[], ll N)
  28. {
  29.     ll i;
  30.     for(i=0; i<N; i++)
  31.         printf("%lld ",A[i]);
  32.     printf("\n");
  33. }*/
  34. int main()
  35. {
  36.     ll T;
  37.     scanf("%lld",&T);
  38.     while(T--)
  39.     {
  40.         ll N,M, X,Y,H,i, j, ans = 0;
  41.         scanf("%lld%lld%lld%lld%lld",&M,&N,&X,&Y,&H);
  42.         memset(B,0,sizeof(B));
  43.         for(i=1; i<=M; i++)
  44.             for(j=1; j<=N; j++)
  45.             scanf("%lld",&A[i][j]);
  46.         priority_queue <point>C;
  47.         point p,q;
  48.         p.val = 0;
  49.         p.X = 1;
  50.         p.Y = 1;
  51.         for(i=0; i<=M; i++)
  52.         {
  53.             B[i][0] = 1;
  54.             B[i][N+1] = 1;
  55.         }
  56.         for(i=0; i<=N; i++)
  57.         {
  58.             B[0][i] = 1;
  59.             B[M+1][i] = 1;
  60.         }
  61.         B[M+1][N+1] = 1;
  62.  
  63.         B[1][1] = 1;
  64.         C.push(p);
  65.         ll flag=0;
  66.         while (!C.empty() && !flag)
  67.         {
  68.             q = C.top();
  69.             C.pop();
  70.             if(q.X == X && q.Y == Y)
  71.             {
  72.                 if(q.val == 0)
  73.                     printf("0\n");
  74.                 else
  75.                 printf("%lld\n",q.val-1);
  76.                 flag = 1;
  77.             }
  78.             if(!flag)
  79.             {
  80.                 if(B[q.X +1][q.Y]==0 && abs(A[q.X+1][q.Y] - A[q.X ][q.Y])<=H)
  81.                 {
  82.                     B[q.X +1][q.Y] = 1;
  83.                     p.val = q.val + 1;
  84.                     p.X = q.X + 1;
  85.                     p.Y = q.Y;
  86.                     C.push(p);
  87.                 }
  88.                 if(B[q.X -1][q.Y]==0 && abs(A[q.X-1][q.Y] - A[q.X ][q.Y])<=H)
  89.                 {
  90.                     B[q.X -1][q.Y] = 1;
  91.                     p.val = q.val + 1;
  92.                     p.X = q.X - 1;
  93.                     p.Y = q.Y;
  94.                     C.push(p);
  95.                 }if(B[q.X ][q.Y+1]==0 && abs(A[q.X][q.Y+1] - A[q.X ][q.Y])<=H)
  96.                 {
  97.                     B[q.X][q.Y+1] = 1;
  98.                     p.val = q.val + 1;
  99.                     p.X = q.X ;
  100.                     p.Y = q.Y+1;
  101.                     C.push(p);
  102.                 }if(B[q.X][q.Y-1]==0 && abs(A[q.X][q.Y-1] - A[q.X][q.Y])<=H)
  103.                 {
  104.                     B[q.X][q.Y-1] = 1;
  105.                     p.val = q.val + 1;
  106.                     p.X = q.X ;
  107.                     p.Y = q.Y-1;
  108.                     C.push(p);
  109.                 }
  110.             }
  111.         }
  112.        // dp(0,0,X-1,Y-1,H,M,N);
  113.         if(!flag)
  114.             printf("-1\n");
  115.      /*   for(i=0; i<=M; i++)
  116.         {
  117.         for(j=0;j<=N;j++)
  118.             printf("%lld ",B[i][j]);
  119.             printf("\n");
  120.         }
  121. */    }
  122.  
  123.     return 0;
  124. }
  125.  
Runtime error #stdin #stdout 0s 3316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X84ddc
language:
C++ (gcc 8.3)
created:
9 years 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!