grasshop.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
typedef struct POS {
int x;
int y;
double d;
POS(int _x = -1, int _y = -1, double _d = -1) {
x = _x;
y = _y;
d = _d;
}
} POS;
int r, c, gr, gc, lr, lc;
const int results_max = 10;
int results[results_max];
int results_iter;
int min_jmp;
bool out_of_grid(int x, int y) {
if (x > r || x < 0 || y > c || y < 0) {
return true;
} else {
return false;
}
}
/**
* @return distance from x,y to L
*/
int distance(int x, int y) {
return sqrt(abs(lr-x)*abs(lr-x) + abs(lc-y)*abs(lc-y));
}
POS jump(int x, int y, int dx, int dy) {
int nx, ny;
nx = x + dx;
ny = y + dy;
if (out_of_grid(nx, ny)) {
return POS(-1, -1, -1);
}
return POS(nx, ny, distance(nx, ny));
}
int sgn (double x) {
if (x > 0.)
return 1;
if (x < 0.)
return -1;
return 0;
}
int pos_cmp (const void *a, const void *b) {
const POS *p1 = (const POS *) a;
const POS *p2 = (const POS *) b;
return sgn (p2->d - p1->d);
}
void m_jump(int x, int y, int jumps) {
if (jumps > 10) {
return;
}
if (results_iter == results_max) {
return;
}
POS p[8];
int iter = 0;
POS tmp;
// printf("a");
for (int i = -1; i <= 1; i += 1) {
for (int j = -1; j <= 1; j += 1) {
if (i == 0 && j == 0) {
continue;
}
p[iter++] = jump(x, y, i, j);
//printf("x: %d, y: %d, i:%d, j: %d, px: %d, py: %d\n", x, y, i, j, p[iter - 1].x, p[iter -1].y);
}
}
// printf("b");
// qsort (p, 8, sizeof *p, pos_cmp);
//printf("c");
for (int i = 0; i < 8; i += 1) {
if (p[i].x == -1) {
continue;
}
// printf("jmp: %d, i:%d, px: %d, py: %d\n", jumps, i, p[i].x, p[i].y);
if (p[i].x == lr && p[i].y == lc) {
if (jumps + 1 < min_jmp) {
printf("yay %d\n", jumps);
min_jmp = jumps + 1;
results[results_iter++] = jumps + 1;
if (results_iter == results_max) {
return;
}
}
}
}
// printf("d");
for (int i = 7; i >= 0; i -= 1) {
if (p[i].x == -1) {
continue;
}
m_jump(p[i].x, p[i].y, jumps + 1);
}
}
int tabulka[7][7] = { { 0, 3, 2, 3, 2, 3, 4},
{ 3, 2, 1, 2, 3, 4, 0},
{ 2, 1, 4, 3, 2, 0, 0},
{ 3, 2, 3, 2, 0, 0, 0},
{ 2, 3, 2, 0, 0, 0, 0},
{ 3, 4, 0, 0, 0, 0, 0},
{ 4, 0, 0, 0, 0, 0, 0}};
int main(int argc, char** argv) {
while (scanf("%d%d%d%d%d%d", &r, &c, &gr, &gc, &lr, &lc) == 6) {
int jumps = 0;
int orig_gr = gr;
int orig_gc = gc;
while(abs(gr - lr) + abs(gc - lc) > 6)
{
if (abs(gr - lr) > abs(gc - lc))
{
if (gr > lr)
{
gr -= 2;
if (gc > lc)
{
gc--;
}
else gc++;
}
jumps++;
}
else
{
if (gc > lc)
{
gc -= 2;
if (gr > lr)
{
gr--;
}
else gr++;
}
jumps++;
}
}
if ( r < 3 || c < 3)
{
printf("impossible\n");
continue;
}
jumps += tabulka[abs(gr - lr)][abs(gc - lc)];
printf("%d\n", jumps);
}
return 0;
}