grasshop.c

#include <stdio.h>
 
int hops[100][100];
int relative_hops[8][2] = {
		{ -2, -1 },
		{ -2, 1 },
		{ -1, 2 },
		{ 1, 2 },
		{ 2, 1 },
		{ 2, -1 },
		{ 1, -2 },
		{ -1, -2 }
};
 
int main(void) {
		int rows, cols, start_row, start_col, end_row, end_col, i, j, k, hopped, hop_i, hop_j;
 
		while (scanf("%d %d %d %d %d %d", &rows, &cols, &start_row, &start_col, &end_row, &end_col) == 6) {
				for (i = 0; i < rows; ++i) {
						for (j = 0; j < cols; ++j) {
								hops[i][j] = -1;
						}
				}
 
				hopped = 1;
				hops[start_row - 1][start_col - 1] = 0;
 
				while (hopped) {
						hopped = 0;
 
						/*
						for (i = 0; i < rows; ++i) {
								for (j = 0; j < cols; ++j) {
										printf("%d ", hops[i][j]);
								}
 
								printf("\n");
						}
 
						printf("\n");
						*/
 
						for (i = 0; i < rows; ++i) {
								for (j = 0; j < cols; ++j) {
										if (hops[i][j] > -1) {
												for (k = 0; k < 8; ++k) {
														hop_i = i + relative_hops[k][0];
														hop_j = j + relative_hops[k][1];
 
														if (hop_i >= 0 && hop_i < rows && hop_j >= 0 && hop_j < cols) {
																if (hops[i][j] + 1 < hops[hop_i][hop_j] ||
																		hops[hop_i][hop_j] == -1)
																{
																		hops[hop_i][hop_j] = hops[i][j] + 1;
																		++hopped;
																}
														}
												}
										}
								}
						}
 
						/*
						for (i = 0; i < rows; ++i) {
								for (j = 0; j < cols; ++j) {
										printf("%d ", hops[i][j]);
								}
 
								printf("\n");
						}
 
						printf("-------------\n");
						*/
				}
 
				if (hops[end_row - 1][end_col - 1] == -1) {
						printf("impossible\n");
				} else {
						printf("%d\n", hops[end_row - 1][end_col - 1]);
				}
		}
 
		return 0;
}