grasshop.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair <int, int> PII;
typedef long long int LL;
typedef vector <int> VI;
typedef vector <LL> VLL;
#define FOR(i, a, b) for ( int i = a; i < b; ++i )
#define FORD(i, a, b) for ( int i = a-1; i >= 0; --i )
#define FILL(x, v, n) for ( int _i = 0; _i < n; ++_i ) x[_i] = v;
int dx[ 8 ] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int dy[ 8 ] = { 1, -1, 1, -1, 2, -2, 2, -2 };
bool vis[ 101 ][ 101 ];
struct State
{
int x, y, d;
};
int main()
{
int R, C, gr, gc, lr, lc;
while ( scanf( "%d %d %d %d %d %d", &R, &C, &gr, &gc, &lr, &lc ) == 6 )
{
int res = -1;
queue< State > q;
State st;
st.x = gc;
st.y = gr;
st.d = 0;
q.push( st );
while ( !q.empty() )
{
State s = q.front();
q.pop();
if ( s.x == lc && s.y == lr )
{
res = s.d;
break;
}
FOR(i,0,R)FOR(j,0,C) vis[ i ][ j ] = false;
State ns;
FOR(i,0,8)
{
ns.x = s.x + dx[i];
ns.y = s.y + dy[i];
ns.d = s.d + 1;
if ( ns.x < 0 || ns.y < 0 || ns.x >= C || ns.y >= R || vis[ ns.y ][ ns.x ] )
continue;
vis[ ns.y ][ ns.x ] = true;
q.push( ns );
}
}
if ( res == -1 )
printf( "impossible\n" );
else
printf( "%d\n", res );
}
return 0;
}