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;
}
 

grasshop.cpp