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