fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4.  
  5. int n , m , x, y , d , test ;
  6. int b[111][111];
  7. map < pair < int , int > , int > id ;
  8. void pre(){
  9.  id.clear() ;
  10.  int c = 1 ;
  11.  for( int i = 1 ; i <= n ; i++)
  12.  for ( int j = 1 ; j <= m ; j++)
  13.  id[ make_pair( i , j )] = c++ ;
  14.  
  15. }
  16. int dr[] = { -1,0,1,0} ;
  17. int dc[] = { 0 ,1, 0, -1} ;
  18. bool valid ( int i , int j){
  19.   return  ( i >= 1 && i <= n && j >= 1 && j <= m );
  20. }
  21. vector < int > adj [11111] ;
  22. int dis [11111] ;
  23.  
  24.  
  25.  
  26. int main(){
  27. pre() ;
  28. int i , j, k, l;
  29. cin >> test ;
  30. while ( test-- ){
  31.  
  32.      cin >> n >> m >> x >> y >> d ;
  33.      pre() ;
  34.      for( i = 1 ; i <= n ; i++)
  35.         for( j = 1 ; j <= m ; j++)
  36.         cin >> b [i][j] ;
  37.  
  38.      if( x == 1 && y == 1){
  39.         cout <<"0\n" ; continue;
  40.  
  41.      }
  42.  
  43.      for ( i = 0 ; i <= 11000 ; i++)
  44.      adj[i].clear() ;
  45.  
  46.      memset ( dis, -1, sizeof dis) ;
  47.      for ( i = 1 ; i <= n  ; i++)
  48.      for ( j = 1 ; j <= m ; j++ ){
  49.  
  50.            for ( k = 0 ; k < 4 ; k++){
  51.                int tr = i + dr[k] ; int tc = j + dc[k] ;
  52.                if( valid( tr,tc))
  53.                if( abs( b[tr][tc] - b[i][j]) <= d){
  54.                   adj[ id [ make_pair(i,j)]].push_back ( id[ make_pair( tr,tc) ] ) ;
  55.                }
  56.            }
  57.      }
  58.      /*
  59.      for ( i = 1 ; i <= n*m ; i++ ){
  60.          cout << i <<" ";
  61.          for( j = 0 ; j < adj[i].size() ; j++)
  62.          cout <<" "<<adj[i][j] ;
  63.          cout << endl;
  64.      }
  65. */
  66.  
  67.      queue < int > q ;
  68.      dis[ id[ make_pair(1,1)] ] = 0;
  69.      q.push( id[ make_pair(1,1)] ) ;
  70.      while ( !q.empty() ){
  71.          int u = q.front() ; q.pop() ;
  72.    //      cout <<"front " << u << endl;
  73.          for ( i = 0 ; i < adj[u].size() ; i++)
  74.          if( dis[ adj[u][i]]  == -1)
  75.          { //  cout <<"o\n" ;
  76.              dis[ adj[u][i]] = dis[u] + 1 ;
  77.              q.push( adj[u][i] );
  78.          }
  79.      }
  80.  
  81.  //    for ( i = 1 ; i <= n*m ; i++){
  82.  //       cout << i <<" "<<dis[i]<<endl;
  83.  //    }
  84.      if( dis[ id[ make_pair(x,y)] ] != -1)
  85.         cout << dis[ id[ make_pair(x,y)] ] - 1 << endl;
  86.      else
  87.         cout <<"-1\n" ;
  88.  
  89. }
  90.  
  91.  
  92.  
  93.  
  94. return  0 ;
  95. }
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
Success #stdin #stdout 0s 2956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/a6qzW6
language:
C++ 4.3.2 (gcc-4.3.2)
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!