grasshop.cpp
//
// File: grasshop.cc
// Author: cteam053
//
// Created on October 27, 2012, 10:55 AM
//
#include <stdlib.h>
#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <climits>
#include <iostream>
#include <list>
using namespace std;
int xmax, ymax;
bool code(int x, int y, int& ret){
if(x <= 0 || y <= 0 || x > xmax || y > ymax)
return false;
ret = 1000*x + y;
return true;
}
int main(int argc, char** argv) {
int R, C, Gr, Gc, Lr, Lc;
list<int> sData;
list<int> len;
int length = -1;
int tmp, x, y, ret, request;
while(1){
int ret = scanf("%d%d%d%d%d%d", &R, &C, &Gr, &Gc, &Lr, &Lc);
if(ret != 6)
return 0;
xmax = R;
ymax = C;
code(Lr, Lc, request);
code(Gr, Gc, ret);
len.clear();
len.push_back(0);
sData.clear();
sData.push_back(ret);
while(!sData.empty()){
tmp = *(sData.begin());
sData.pop_front();
length = *(len.begin());
len.pop_front();
if(tmp == request)
break;
x = tmp / 1000;
y = tmp % 1000;
if(code(x-2, y-1, ret)){
sData.push_back(ret);
len.push_back(length+1);
}
if(code(x-2, y+1, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x-1, y+2, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x+1, y+2, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x+2, y+1, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x+2, y-1, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x+1, y-2, ret)){
len.push_back(length+1);
sData.push_back(ret);}
if(code(x-1, y-2, ret)){
len.push_back(length+1);
sData.push_back(ret);}
}
if(length == 0)
printf("impossible\n");
else
printf("%d\n", length);
}
return (0);
}