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