grasshop.cpp

#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
 
struct Pos
{
	int x;
	int y;
};
 
static const int MAX = 105;
int pole[MAX][MAX];
 
queue<Pos> fronta;
 
 
 
void pridej ( const Pos & tmp){
    Pos nov;
    nov.x = tmp.x-1;
    nov.y = tmp.y+2;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
	       //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
    nov.x -= 1;
    nov.y -= 1;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
 
    nov.y -= 2;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
    nov.x +=1;
    nov.y -=1;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
    nov.x +=2;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
    nov.x +=1;
    nov.y +=1;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}   
	}
    nov.y +=2;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
    nov.x -=1;
    nov.y +=1;
	if (pole[nov.x+1][nov.y+1])
	{
		if ( pole[nov.x+1][nov.y+1] == -1 || pole[nov.x+1][nov.y+1] > (pole[tmp.x+1][tmp.y+1] +1) ) {
 
	 //printf("%d %d\n", nov.x, nov.y);
		   fronta.push(nov);
		   pole[nov.x+1][nov.y+1] = pole[tmp.x+1][tmp.y+1] +1;
		}
	}
 
}
void print(int x, int y);
void nuluj(int x, int y){
 
  for (int i = 2; i <= x+1; i++)
    for ( int j=2; j <= y+1; j++)
      pole[i][j]=-1;
 
 
	for ( int j=0; j <= y+3; j++)
      pole[x+2][j]=pole[x+3][j]=0;
 
    for ( int j=0; j <= x+3; j++)
      pole[j][y+2]=pole[j][y+3]=0;
 
     //print(x,y); 
 
}
void print(int x, int y) {
 
  for (int i = 0; i <= x+3; i++){
    for ( int j=0; j <= y+3; j++)
      printf("%d  ",pole[i][j]);
 
      printf("\n");
      }
 
}
 
int main(){
	int        r,s,gr,gs,ls,lr;
	Pos        tmp;
 
	while (scanf("%d %d %d %d %d %d", &r, &s, &gr, &gs, &lr, &ls) == 6)
	{
	    nuluj(s,r);
		tmp.y = gr;
		tmp.x = gs;
		pole[tmp.x+1][tmp.y+1]=0;
		fronta.push(tmp);
 
		while (!fronta.empty())
		{
		    ////printf("[%d,%d]%d\n", tmp.x, tmp.y, pole[tmp.x+1][tmp.y+1]);
			tmp = fronta.front();
			fronta.pop();
			if ( tmp.y == lr && tmp.x == ls ) {
 
			   break;	
			   }
			pridej(tmp);
		}
	//printf("------\n");
	//print(s,r);	
	if ( tmp.x == ls && tmp.y == lr ){
 
	  printf("%d\n", pole[tmp.x+1][tmp.y+1]);
	  }
	else
	  printf("impossible\n");
 
	while (!fronta.empty()) fronta.pop();
	}
	return 0;
}