fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define endl cout<<"\n";
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define op freopen
  9. #define TXT "test"
  10. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  11.  
  12. using namespace std;
  13. int n,m,a[1005][1005],u1,v1,u2,v2;
  14. int dx[]={1,-1,0,0};
  15. int dy[]={0,0,1,-1};
  16. bool vs[1005][1005];
  17. bool check(int m)
  18. {
  19.     int ans;
  20.     memset(vs,false,sizeof vs);
  21.     queue<pii> q;
  22.     pii c;
  23.     q.push({u1,v1});
  24.     vs[u1][v1]=1;
  25.     int x,y,nx,ny;
  26.     while(!q.empty())
  27.     {
  28.         c=q.front();
  29.         x=c.fi;
  30.         y=c.se;
  31.         q.pop();
  32.         if(x==u2&&y==v2)
  33.         {
  34.             return 1;
  35.         }
  36.         for(int i=0;i<4;i++)
  37.         {
  38.             nx=dx[i]+x;
  39.             ny=dy[i]+y;
  40.             if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vs[nx][ny]&&abs(a[x][y]-a[nx][ny])<=m)
  41.             {
  42.                 vs[nx][ny]=1;
  43.                 q.push({nx,ny});
  44.             }
  45.         }
  46.     }
  47.     return 0;
  48. }
  49. void bs(int l,int r)
  50. {
  51.     int m,ans=-1;
  52.     while(l<=r)
  53.     {
  54.         m=(l+r)>>1;
  55.         if(check(m))
  56.         {
  57.             ans=m;
  58.             r=m-1;
  59.         }
  60.         else
  61.         {
  62.             l=m+1;
  63.         }
  64.     }
  65.     cout<<ans;
  66. }
  67. main()
  68. {
  69.     cin>>n>>m>>u1>>v1>>u2>>v2;
  70.     for(int i=1;i<=n;i++)
  71.     {
  72.         for(int j=1;j<=m;j++)
  73.         {
  74.             cin>>a[i][j];
  75.         }
  76.     }
  77.     bs(0,1e9);
  78. }
  79.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xsC2qx
language:
C++ (gcc 8.3)
created:
10 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!