grasshop.c

#include <stdlib.h>
#include <stdio.h>
 
#define NOT_VISITED -1
 
int R, C, GR, GC, LR, LC;
/* R, C ... area size */
int area[102][102]; /* R-major */
 
typedef struct {unsigned char r, c;} point;
typedef struct {point list[102*102]; int len;} data;
 
data aa, bb;
 
int in_grid(point x)
{
	return x.r >= 1 && x.r <= R && x.c >= 1 && x.c <= C;
}
 
int main(void)
{
	int i, step, row, col, j;
	point *p;
	int *len_ptr;
	point dest[8];
	int flag;
	data *a, *b, *tmp;
 
	while (scanf("%d %d %d %d %d %d ", &R, &C, &GR, &GC, &LR, &LC) == 6) {
		a = &aa;
		b = &bb;
		for (i = 0; i < 102*102; ++i)
			((int*)(area))[i] = NOT_VISITED;
		area[GR][GC] = 0;
 
		a->len = 0;
		b->len = 0;
 
		a->list[0].r = GR;
		a->list[0].c = GC;
		a->len = 1;
 
		for (step = 1; ; ++step)
		{
			b->len = 0;
			flag = 0;
			for (i = 0; i < a->len; ++i)
			{
				row = a->list[i].r;
				col = a->list[i].c;
				/*
				dest = { {row+1, col+2}, {row+1, col-2}, {row-1, col+2}, {row-1, col-2},
						 {row+2, col+1}, {row+2, col-1}, {row-2, col+1}, {row-2, col-1} };
				*/
				dest[0].r = row+1;
				dest[0].c = col+2;
 
				dest[1].r = row-1;
				dest[1].c = col+2;
 
				dest[2].r = row+1;
				dest[2].c = col-2;
 
				dest[3].r = row-1;
				dest[3].c = col-2;
 
				dest[4].r = row+2;
				dest[4].c = col+1;
 
				dest[5].r = row-2;
				dest[5].c = col+1;
 
				dest[6].r = row+2;
				dest[6].c = col-1;
 
				dest[7].r = row-2;
				dest[7].c = col-1;
 
 
				for (j = 0; j < 8; ++j)
				{
					if (in_grid(dest[j])) {
						if (area[ dest[j].r ][ dest[j].c ] == NOT_VISITED) {
							area[ dest[j].r ][ dest[j].c ] = step;
							flag = 1;
							b->list[ b->len++ ] = dest[j];
							if (dest[j].r == LR && dest[j].c == LC) {
								printf("%d\n", step);
								goto endloop;
							}
						}
					}
				}
 
			}
			if (flag == 0) {
				printf("impossible\n");
				goto endloop;
			}
			tmp = b;
			b = a;
			a = tmp;
		}
endloop:
	;
	}
	return 0;
}