grasshop.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int q[120000];
int qrp;
int qwp;
int visited[200][200];
int r,c;
 
void qi(int x, int y, int d) {
	if (visited[x][y]) return;
	if (x < 1 || y < 1) return;
	if (x > r || y > c) return;
	visited[x][y] = 1;
	q[qwp++] = x;
	q[qwp++] = y;
	q[qwp++] = d;
}
 
void qr(int *x, int *y, int *d) {
	*x = q[qrp++];
	*y = q[qrp++];
	*d = q[qrp++];
}
 
int main(int argc, char **argv)
{
	int gr,gc,lr,lc;
 
	int cr,cc,cd;
 
	while (1) {
		scanf("%d %d %d %d %d %d", &r, &c, &gr, &gc, &lr, &lc);
		if (feof(stdin))
			break;
		qrp = 0;
		qwp = 0;
		memset(visited, 0, sizeof(int)*200*200);
		qi(gr,gc,0);
		while (qrp < qwp) {
			qr(&cr,&cc,&cd);
			if (cr==lr && cc==lc) {
				printf("%d\n", cd);
				break;
			}
			qi(cr-2, cc-1, cd+1);
			qi(cr-1, cc-2, cd+1);
			qi(cr-2, cc+1, cd+1);
			qi(cr-1, cc+2, cd+1);
			qi(cr+2, cc-1, cd+1);
			qi(cr+1, cc-2, cd+1);
			qi(cr+2, cc+1, cd+1);
			qi(cr+1, cc+2, cd+1);
		}
		if (qrp >= qwp) printf("impossible\n");
	}
	return 0;
}