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