grasshop.cpp

#include<stdio.h>
#include<stdlib.h>
#include<queue>
 
struct Pad {
	bool visited;
	int steps;
};
 
struct Pos {
	int x, y, steps;
	Pos(){};
	Pos(int xp, int yp, int stepsp) {
	x = xp; y = yp; steps = stepsp;		
	}
};
 
class GrassHop {
	Pad grid[104][104];
	int destx, desty;
	int gridx, gridy;
	int gregx, gregy;
	std::queue<Pos> myq; 
	public:
		GrassHop();
		bool Load();
		//void Resetgrid(int x, int y);
		void Solve();
};
 
GrassHop::GrassHop() {
	for(int i = 0; i < 104; i++){
		grid[i][0].visited = true;
		grid[i][1].visited = true;
		grid[0][i].visited = true;
		grid[1][i].visited = true;
		grid[i][103].visited = true;
		grid[i][102].visited = true;
		grid[103][i].visited = true;
		grid[102][i].visited = true;
	}
 
}
 
bool GrassHop::Load() {
	int i, j;	
	if(scanf("%d%d%d%d%d%d ", &gridx, &gridy, &gregx, &gregy, &destx, &desty) != 6) return false;
	/* init cycles */	
	for(j=2; j < gridy+2; j++) {	
		for(i = 2; i < gridx+2; i++) {
			grid[i][j].visited = false;		
		}
		for(int k = 0; k < 2; k++, i++) {
			grid[i][j].visited = true;
		}	
	}
	for(i=2; i< gridx+4; i++)
		for(j=gridy+2; j<gridy+4; j++)
			grid[i][j].visited=true;
 
 
	gregx += 1;
	gregy += 1;
	destx += 1;
	desty += 1;
	/*
	for(i = 0; i < 20; i++) {
		for(j = 0; j< 20; j++) {
			printf("%c", grid[i][j].visited ? '1' : '0');
		}
		printf("\n");
	}*/
 
	while(!myq.empty()) myq.pop();
	myq.push(Pos(gregx,gregy,0));
	return true;
}
 
void GrassHop::Solve() {
	Pos p;
	while(!myq.empty()) {
		p = myq.front();
		myq.pop();
		//printf("%d %d %c\n", p.x, p.y, grid[p.x][p.y].visited ? '1' : '0');
		if(grid[p.x][p.y].visited) continue;
		grid[p.x][p.y].visited = true;
		grid[p.x][p.y].steps = p.steps;
		if(p.x == destx && p.y == desty) break;
		p.steps++;
		myq.push(Pos(p.x+2,p.y+1,p.steps));
		myq.push(Pos(p.x+2,p.y-1,p.steps));
		myq.push(Pos(p.x-2,p.y+1,p.steps));
		myq.push(Pos(p.x-2,p.y-1,p.steps));
		myq.push(Pos(p.x+1,p.y+2,p.steps));
		myq.push(Pos(p.x+1,p.y-2,p.steps));
		myq.push(Pos(p.x-1,p.y+2,p.steps));
		myq.push(Pos(p.x-1,p.y-2,p.steps));
	}
 
	if(grid[destx][desty].visited){
		printf("%d\n",grid[destx][desty].steps);
	} else {
		printf("impossible\n");
	}
}
int main(int argc, char * argv[]) {
	GrassHop g;
	while(g.Load()) g.Solve();
	return 0;
}