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]);
}
}
}