grasshop.cpp
/*
* File: grasshop.c
* Author: cteam057
*
* Created on October 27, 2012, 11:02 AM
*/
#include <stdio.h>
#include <stdlib.h>
#include <queue>
/*
*
*/
int r, c, gr, gc, lr, lc;
int i, j, begin, end, nalezeno, qsize;
int ** pole;
int *fronta;
int trysq(int a, int b) {
if(fronta[begin%qsize]+a>0 && fronta[begin%qsize]+a<=r && fronta[(begin+1)%qsize]+b>0 && fronta[(begin+1)%qsize]+b<=c
&& pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b]==-1) {
fronta[end%qsize] = fronta[begin%qsize]+a;
end++;
fronta[end%qsize] = fronta[(begin+1)%qsize]+b;
end++;
pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b] = pole[fronta[begin]][fronta[begin+1]] +1;
if(fronta[begin%qsize]+a == lr && fronta[(begin+1)%qsize]+b == lc) {
printf("%d\n", pole[fronta[begin%qsize]+a][fronta[(begin+1)%qsize]+b]);
nalezeno = 1;
return 1;
}
}
return 0;
}
int main(int argc, char** argv) {
while(scanf("%d %d %d %d %d %d", &r, &c, &gr, &gc, &lr, &lc)==6) {
pole = (int **) malloc((r+1)*sizeof(int*));
for(i = 1; i <= r; i++) {
pole[i] = (int *) malloc((c+1)*sizeof(int));
for (j = 1; j <= c; j++) pole[i][j] = -1;
}
begin = 0;
end = 2;
qsize = 4*r*c;
fronta = (int *) malloc (4*r*c*sizeof(int));
fronta[0] = gr;
fronta[1] = gc;
pole[gr][gc] = 0;
nalezeno = 0;
while(begin!=end) {
if(trysq(-1, -2)) break;
if(trysq(1, -2)) break;
if(trysq(-1, 2)) break;
if(trysq(1, 2)) break;
if(trysq(-2, -1)) break;
if(trysq(-2, 1)) break;
if(trysq(2, -1)) break;
if(trysq(2, 1)) break;
begin+=2;
}
if(!nalezeno) printf("impossible\n");
free(fronta);
for(i = 1; i <=r; i++) {
free(pole[i]);
}
free(pole);
}
return 0;
}