grasshop.c

/*
 * File:   grasshop.c
 * Author: cteam066
 *
 * Created on October 27, 2012, 11:41 AM
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
#define GRID_MAX 100
#define GRID_SIDE GRID_MAX + 2
 
int grid[GRID_SIDE][GRID_SIDE];
int x_side;
int y_side;
 
void reset(){
    int i = 0;
    for ( i = 0; i < GRID_SIDE; ++i )
        memset( grid[i], 0, sizeof(int) * GRID_SIDE );
}
 
void traverse( int x, int y, int step ) {
    if ( x < 1 || y < 1 || x > x_side || y > y_side )
        return;
 
    if ( grid[x][y] && step > grid[x][y] )
        return;
 
    grid[x][y] = step;
 
    int nextStep = step + 1;
 
    traverse( x + 2, y + 1, nextStep );
    traverse( x + 2, y - 1, nextStep );
 
    traverse( x - 2, y + 1, nextStep );
    traverse( x - 2, y - 1, nextStep );
 
    traverse( x + 1, y + 2, nextStep );
    traverse( x + 1, y - 2, nextStep );
 
    traverse( x - 1, y + 2, nextStep );
    traverse( x - 1, y - 2, nextStep );
}
 
 
/*
 *
 */
int main(int argc, char** argv) {
 
    int x_start, y_start;
    int x_dest, y_dest;
 
    while( scanf("%d %d %d %d %d %d",
            &x_side, &y_side, &x_start, &y_start, &x_dest, &y_dest) == 6){
 
        reset();
        traverse(x_start, y_start, 1);
        int result = grid[x_dest][y_dest];
        if ( result )
            printf("%d\n", result - 1);
        else 
            printf("impossible\n");
    }
 
    return (EXIT_SUCCESS);
}