grasshop.cpp
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
bool done=false;
bool inboard(int i, int j,int x,int y){
if(i>0 && i<=x && j>0 && j<=y)
return true;
else
return false;
}
class uzol{
public:
int step;
int x,y;
};
int step(int x, int y,int step,queue<uzol> & fronta,vector<vector<int> > & board){
if(board[x][y]==-2){
printf("%d\n",step+1);
done=true;
return 0; //koniec
}else if(board[x][y]==-1){
board[x][y]=step+1;
} else{
if(board[x][y]>step+1)
board[x][y]=step+1;
}
uzol r;
r.x=x;
r.y=y;
r.step=step+1;
fronta.push(r);
return 1;
}
int main(){
int a,b,c,d,e,f;
vector<vector<int> > board;
board.resize(101);
for(int i=0;i<101;i++)
board[i].resize(101);
while(scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)==6){
done=false;
queue<uzol> fronta;
for(int i=0;i<=a;i++){
for(int j=0;j<=b;j++){
board[a][b]=-1;
}
}
board[e][f]=-2;
board[c][d]=0;
uzol f;
f.step=0;
f.x=c;
f.y=d;
fronta.push(f);
while(fronta.size()>0){
uzol node=fronta.front();
fronta.pop();
if(inboard(node.x+2, node.y+1,a,b)){
if(step(node.x+2, node.y+1,node.step,fronta,board)==0)break;
}
if(inboard(node.x+2, node.y-1,a,b)){
if(step(node.x+2, node.y-1,node.step,fronta,board)==0)break;
}
if(inboard(node.x+1, node.y+2,a,b)){
if(step(node.x+1, node.y+2,node.step,fronta,board)==0)break;
}
if(inboard(node.x+1, node.y-2,a,b)){
if(step(node.x+1, node.y-2,node.step,fronta,board)==0)break;
}
if(inboard(node.x-2, node.y+1,a,b)){
if(step(node.x-2, node.y+1,node.step,fronta,board)==0)break;
}
if(inboard(node.x-2, node.y-1,a,b)){
if(step(node.x-2, node.y-1,node.step,fronta,board)==0)break;
}
if(inboard(node.x-1, node.y-2,a,b)){
if(step(node.x-1, node.y-2,node.step,fronta,board)==0)break;
}
if(inboard(node.x-1, node.y+2,a,b)){
if(step(node.x-1, node.y+2,node.step,fronta,board)==0)break;
}
}
if(done==false)
printf("impossible\n");
}
return 0;
}