Go to diff to previous submission
/* * 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; } if(gr == lr && gc == lc) { printf("0\n"); continue; } 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; }