grasshopper.cpp

#include <cstdio>
#include <cstdlib>
#include <queue>
#define INF 999999
 
using namespace std;
 
unsigned int map[100][100];
 
unsigned int dir[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
 
typedef struct point{
  point( int a, int b ) : x(a), y(b){}
  int x, y;
} t_point;
 
inline bool canHop( int r, int s, int x, int y ) {
   return (x < r) && ( y < s) && ( x >= 0) && ( y >= 0) && (map[x][y]==INF);
}
 
int main( int argc, char ** argv ) {
  int r,c,gr,gc,lr,lc;
  queue<t_point> q;
  while( scanf("%d %d %d %d %d %d",&r,&c,&gr,&gc,&lr,&lc) ) {
    for( int i = 0; i < r; i++) 
      for( int j = 0; j < c; j++ ) 
	map[i][j] = INF;
 
      //q.clear();
      //r--;c--;
      gr--;gc--;
      lr--;lc--;
 
	map[gr][gc] = 0;
        t_point point(gr,gc);
	q.push( point );
 
        while( !q.empty() ) {
	   point = q.front();
	   q.pop();
	   for( int i = 0; i < 8; i++) {
	     t_point tmp( point.x + dir[i][0], point.y + dir[i][1]);
	    if( canHop(r,c,tmp.x,tmp.y) ) {
	      map[ tmp.x][ tmp.y ] = map[ point.x ][ point.y ] + 1;
	     // printf("%d %d\n", tmp.x + 1, tmp.y + 1);
	      q.push( tmp );
	    }
	   }
	}
 
	if( map[lr][lc] == INF ) {
	  printf("impossible\n");
	} else {
	  printf("%d\n",map[lr][lc]);
	}
 
  }
}