grasshop.cpp

#include <cstdio>
#include <cstring>
 
using namespace std;
 
void enqueue(int x, int y, int distance, int queueX[10000], int queueY[10000], int &queueLen, int dist[100][100], int rows, int cols) {
	if(dist[x][y] != 0) return;
	if(x < 0 || x >= cols) return;
	if(y < 0 || y >= rows) return;
	queueX[queueLen] = x;
	queueY[queueLen] = y;
	dist[x][y] = distance + 1;
	++queueLen;
}
 
int main(void) {
	while(true) {
		int rows, cols, sx, sy, tx, ty;
 
		if(scanf("%d%d%d%d%d%d\n", &rows, &cols, &sx, &sy, &tx, &ty) != 6) {
			break;
		}
 
		--sx;
		--sy;
		--tx;
		--ty;
 
		int dist[100][100];
		for(int i = 0; i < cols; ++i) {
			for(int j = 0; j < rows; ++j) {
				dist[i][j] = 0;
			}
		}
 
 
		int queueX[10000], queueY[10000];
		int queueLen = 1;
		int queuePos = 0;
 
		queueX[0] = sx;
		queueY[0] = sy;
		dist[sx][sy] = 1;
 
		int curX, curY, curDist;
 
		while(queuePos < queueLen) {
			curX = queueX[queuePos];
			curY = queueY[queuePos];
			curDist = dist[curX][curY];
 
			if(curX == tx && curY == ty) break;
 
			enqueue(curX + 2, curY + 1, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX + 2, curY - 1, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX + 1, curY + 2, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX + 1, curY - 2, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX - 1, curY + 2, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX - 1, curY - 2, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX - 2, curY + 1, curDist, queueX, queueY, queueLen, dist, rows, cols);
			enqueue(curX - 2, curY - 1, curDist, queueX, queueY, queueLen, dist, rows, cols);
 
			++queuePos;
		}
 
		int minDist = dist[tx][ty];
 
		if(minDist == 0) {
			printf("impossible\n");
		}
		else {
			printf("%d\n", minDist - 1);
		}
	}
}