grasshop.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
int pole[111][111];
int R, C, GR, GC, LR, LC;
struct Point{
int r, c;
};
bool solve() {
if (scanf("%d%d%d%d%d%d",&R,&C,&GR,&GC,&LR,&LC)<0) return false;
--GR,--GC,--LR,--LC;
for(int i=0;i<R;++i)
for(int j=0;j<C;++j){
pole[i][j] = INF;
}
int dc[] = {1,2,2,1,-1,-2,-2,-1};
int dr[] = {-2,-1,1,2,2,1,-1,-2};
queue<Point> fronta;
fronta.push((Point){GR,GC});
pole[GR][GC] = 0;
while(!fronta.empty()){
Point pc = fronta.front();
fronta.pop();
if(pc.r == LR && pc.c==LC){
printf("%d\n", pole[pc.r][pc.c]);
return true;
}
for(int d=0;d<8;++d){
Point np = pc;
np.r += dr[d];
np.c+=dc[d];
if(np.c<0 || np.r<0 ||np.c>=C || np.r>=R)
continue;
if(pole[np.r][np.c]!=INF)
continue;
pole[np.r][np.c] = pole[pc.r][pc.c]+1;
fronta.push(np);
}
}
printf("impossible\n");
return true;
}
int main() {
while(solve());
return 0;
}