grasshop.cpp

#include <cstdio>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
bool ** bitmap;
int R, C, Gr, Gc, Lr, Lc, steps, min_;
 
bool rek(int x, int y, int steps)
{
	//bitmap[x][y];
	if (x == Lr && y == Lc)
	{
		if (min_ > steps) min_ = steps;
		return true;
	}
	bool ret = false;
	steps++;
	if ((R > C && steps > R) || (C >= R && steps > C)) return false;
	if (x+2 <  R && y+1 <  C && bitmap[x+2][y+1]) ret |= rek(x+2, y+1, steps);
	if (x+2 <  R && y-1 >= 0 && bitmap[x+2][y-1]) ret |= rek(x+2, y-1, steps);
	if (x-2 >= 0 && y+1 <  C && bitmap[x-2][y+1]) ret |= rek(x-2, y+1, steps);
	if (x-2 >= 0 && y-1 >= 0 && bitmap[x-2][y-1]) ret |= rek(x-2, y-1, steps);
 
	if (y+2 <  C && x+1 <  R && bitmap[x+1][y+2]) ret |= rek(x+1, y+2, steps);
	if (y+2 <  C && x-1 >= 0 && bitmap[x-1][y+2]) ret |= rek(x-1, y+2, steps);
	if (y-2 >= 0 && x+1 <  R && bitmap[x+1][y-2]) ret |= rek(x+1, y-2, steps);
	if (y-2 >= 0 && x-1 >= 0 && bitmap[x-1][y-2]) ret |= rek(x-1, y-2, steps);
	return ret;
}
 
int main()
{
	while (cin >> R >> C >> Gr >> Gc >> Lr >> Lc)
	{
		bitmap = (bool **) malloc(sizeof(bool *) * R);
		for (int i=0; i<R; i++)
		{
			bitmap[i] = (bool *) malloc(sizeof(bool) * C);
			for (int j=0; j<C; j++)
				bitmap[i][j] = true;
		}
		Gr--; Gc--; Lr--; Lc--;
		min_ = R+C;
		if (!rek(Gr, Gc, 0)) cout << "impossible" << endl;
		else cout << min_ << endl;
		for (int i=0; i<R; i++)
			free(bitmap[i]);
		free(bitmap);
	}
	return 0;
}