grasshop.cpp
#include <stdio.h>
#include <string.h>
int row[10001];
int col[10001];
int step[10001];
bool map[101][101];
int now,last;
int r,c,lr,lc;
int checkAndAdd(int x, int y) {
x += row[now];
y += col[now];
if(x > 0 && x<=r && y>0 && y<=c &&!map[x][y]) {
if(x==lr && y==lc) {
return(step[now]+1);
}
row[++last] = x;
col[last] = y;
step[last] = step[now]+1;
map[x][y]=true;
}
return 0;
}
int main() {
int result;
bool found;
while(scanf("%d %d %d %d %d %d",&r, &c, row+0, col+0, &lr, &lc)>0) {
if(row[0]==lr && row[0]==lc){
printf("0\n");
continue;
}
found=false;
now=0;
last=0;
memset(map,0,101*101*sizeof(bool));
map[row[0]][col[0]]=true;
step[0]=0;
result=0;
while(now<=last && !found) {
result = checkAndAdd(1,2);
if(!result) result = checkAndAdd(2,1);
if(!result) result = checkAndAdd(2,-1);
if(!result) result = checkAndAdd(1,-2);
if(!result) result = checkAndAdd(-1,-2);
if(!result) result = checkAndAdd(-2,-1);
if(!result) result = checkAndAdd(-2,1);
if(!result) result = checkAndAdd(-1,2);
if(result) {
printf("%d\n",result);
found = true;
}
now++;
}
if(!found) {
printf("impossible\n");
}
}
return 0;
}