grasshop.cpp

#include <iostream>
#include <list>
 
using namespace std;
int R, C;
int grid[100][100];
list<int> fifo;
 
bool hop(int r, int c, int dr, int dc) {
	if ((r+dr)>=0 && (r+dr)<R && (c+dc)>=0 && (c+dc)<C) {
		if (grid[r+dr][c+dc] == -1)
			return true;
		else if (grid[r+dr][c+dc] == 0) {
			grid[r+dr][c+dc]=grid[r][c]+1;
			fifo.push_back(r+dr);
			fifo.push_back(c+dc);
		}
	}
	return false;
}
 
int main(int argc, char** argv){
	int GR, GC, LR, LC, r, c;
	while (cin >> R >> C) {
		fifo.clear();
		for (r=0; r<R;r++)
			for (c=0; c<C; c++)
				grid[r][c]=0;
		cin >> GR >> GC >> LR >> LC;
		grid[GR][GC]=1;
		grid[LR][LC]=-1;
		fifo.push_back(GR);
		fifo.push_back(GC);
		while (!fifo.empty()) {
			r = fifo.front(); fifo.pop_front();
			c = fifo.front(); fifo.pop_front();
			if (hop(r,c,1,2) || hop(r,c,2,1) || hop(r,c,2,-1) || hop(r,c,1,-2) || 
				hop(r,c,-1,-2) || hop(r,c,-2,-1) || hop(r,c,-2,1) || hop(r,c,-1,2)) {
				cout << grid[r][c] << endl;
				break;
			}
		}
		if (fifo.empty()) cout << "impossible" << endl;
	}
 
	return 0;
}