Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <math.h> int fronta[1000000][3]; int pole[1001][1001]; int a,b,c,d,e,f; int main() { while(scanf("%i %i %i %i %i %i",&a,&b,&c,&d,&e,&f)==6) { for (int i = 1; i <= a; i++) for (int o = 1; o <= b; o++) { pole[i][o] = 0; } int fs = 0; int fl = 0; fronta[fs+fl][0] = c; fronta[fs+fl][1] = d; fronta[fs+fl][2] = 0; fl++; bool ok = false; while (fl > 0) { int x = fronta[fs][0]; int y = fronta[fs][1]; int n = fronta[fs][2]; fs++; fl--; if (x < 1 || x > a || y < 1 || y > b) continue; if (pole[x][y] == 1) continue; //printf("%i %i\n", x,y); pole[x][y] = 1; if (x==e && y == f) { printf("%i\n", n); ok =true; break; } fronta[fs+fl][0] = x + 2; fronta[fs+fl][1] = y + 1; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x + 1; fronta[fs+fl][1] = y + 2; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x - 2; fronta[fs+fl][1] = y - 1; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x - 1; fronta[fs+fl][1] = y - 2; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x - 2; fronta[fs+fl][1] = y + 1; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x - 1; fronta[fs+fl][1] = y + 2; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x + 2; fronta[fs+fl][1] = y - 1; fronta[fs+fl][2] = n + 1; fl++; fronta[fs+fl][0] = x + 1; fronta[fs+fl][1] = y - 2; fronta[fs+fl][2] = n + 1; fl++; } if (ok == false) { printf("impossible\n"); } } return 0; }
--- c4.s843.cteam114.grasshop.cpp.0.grasshop.cpp +++ c4.s947.cteam114.grasshop.cpp.0.grasshop.cpp @@ -3,11 +3,9 @@ #include <math.h> -int pole[200][200]; -int a,b,c,d,e,f; -int cesta(int zx, int zy) -{ - -} + +int fronta[1000000][3]; +int pole[1001][1001]; +int a,b,c,d,e,f; @@ -16,9 +14,95 @@ while(scanf("%i %i %i %i %i %i",&a,&b,&c,&d,&e,&f)==6) { - int dx = abs(c-e); - int dy = abs(f-d); + for (int i = 1; i <= a; i++) + for (int o = 1; o <= b; o++) + { + pole[i][o] = 0; + } + + int fs = 0; + int fl = 0; + + fronta[fs+fl][0] = c; + fronta[fs+fl][1] = d; + fronta[fs+fl][2] = 0; + fl++; + + bool ok = false; + + while (fl > 0) + { + int x = fronta[fs][0]; + int y = fronta[fs][1]; + int n = fronta[fs][2]; + fs++; + fl--; - + if (x < 1 || x > a || y < 1 || y > b) + continue; + + if (pole[x][y] == 1) + continue; + + //printf("%i %i\n", x,y); + + pole[x][y] = 1; + + if (x==e && y == f) + { + printf("%i\n", n); + ok =true; + break; + } + + fronta[fs+fl][0] = x + 2; + fronta[fs+fl][1] = y + 1; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x + 1; + fronta[fs+fl][1] = y + 2; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x - 2; + fronta[fs+fl][1] = y - 1; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x - 1; + fronta[fs+fl][1] = y - 2; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x - 2; + fronta[fs+fl][1] = y + 1; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x - 1; + fronta[fs+fl][1] = y + 2; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x + 2; + fronta[fs+fl][1] = y - 1; + fronta[fs+fl][2] = n + 1; + fl++; + + fronta[fs+fl][0] = x + 1; + fronta[fs+fl][1] = y - 2; + fronta[fs+fl][2] = n + 1; + fl++; + + } + + if (ok == false) + { + printf("impossible\n"); + } + } + + return 0; } \ No newline at end of file