#include <stdio.h>
#include <stdlib.h>
 
#define SIZE 9
int board[SIZE][SIZE];
int INF  = 0x7FFFFFFF;
 
int w[8][2] = {
	{1,2},{1,-2},{-1,2},{-1,-2},
	{2,1},{2,-1},{-2,1},{-2,-1}
};
 
 
int isInRange(int x, int y){
	if((0 <= x && x < SIZE)&&(0 <= y && y < SIZE)){
		return 1;
	}else{
		return 0;
	}
}
 
void update(int cx, int cy, int tx, int ty){
	if(board[tx][ty] != INF && board[cx][cy] > board[tx][ty] + 1){
		board[cx][cy] = board[tx][ty] + 1;
	}
}
 
void print_board(){
	int i,j;
	printf("------- print board -------\n");
	for(i=0; i < SIZE; i++){
		for(j=0; j < SIZE; j++){
			if(board[i][j] == INF){
				printf("INF, ");
			}else{
				printf ("%3d, ", board[i][j]);
			}
		}
		printf("\n");
	}
	printf("------- ----- ----- -------\n");
}
 
void print_route(int X, int Y){
 
	printf(" ---- route -----\n");
 
	int i,j;
	int len = 1;
	int route[SIZE][SIZE];
 
	for(i=0; i < SIZE; i++){
		for(j=0; j <SIZE; j++){
			route[i][j] = 0;
		}
	}
 
	route[X][Y] = len;
 
	while(1){
		int minX, minY;
		int min = INF;
		for(i=0; i < 8; i++){
			if(isInRange(X+w[i][0], Y+w[i][1])){
				if(min > board[X+w[i][0]][Y+w[i][1]]){
					minX = X + w[i][0];
					minY = Y + w[i][1];
					min = board[X+w[i][0]][Y+w[i][1]];
				}
			}
		}
		// increse path walk length
		len++;
		X = minX;
		Y = minY;
		route[X][Y] = len;
 
		if(min == 0){
			break;
		}
	}/*while*/
 
 
	for(i=0; i < SIZE; i++){
		for(j=0; j <SIZE; j++){
 
			if(route[i][j] == 0){
				printf("   , ");
			}else{
				printf("%3d, ", route[i][j]);
			}
		}
		printf("\n");
	}
 
 
}
 
 
 
int getScore(int startX, int startY, int endX, int endY){
	int i,j,k;
 
 
	if(!isInRange(startX, startY)){
		printf("out of range!\n");
		exit(1);	
	}
	if(!isInRange(endX, endY)){
		printf("out of range!\n");
		exit(1);	
	}
 
	// initialize board
	for(i=0; i < SIZE; i++){
		for(j=0; j < SIZE; j++){
			board[i][j] = INF;
		}
	}
	// record minimum cost
	board[endX][endY] = 0;
 
	print_board();
 
	while(1){
 
		int i,j;
		for(i=0; i < SIZE; i++){
			for(j=0; j < SIZE; j++){
				for(k=0; k < 8; k++){
					if(isInRange(i+w[k][0], j+w[k][1])){
						update(i,j,i+w[k][0], j+w[k][1]);
					}
				}
			}
		}
 
		print_board();
 
		if(board[startX][startY] != INF){
			printf("----- find !! -----\n");
			print_route(startX, startY);
			break;
		}
 
	}/*while*/
 
	return board[startX][startY];
}
 
 
 
int main(int argc, const char *argv[])
{
 
	int startX=1, startY=1;
	int endX=7, endY=5;
 
 
	getScore(
		startY,startX,
		endY,endX
		);
 
	return 0;
}

CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgojZGVmaW5lIFNJWkUgOQppbnQgYm9hcmRbU0laRV1bU0laRV07CmludCBJTkYgID0gMHg3RkZGRkZGRjsKCmludCB3WzhdWzJdID0gewoJezEsMn0sezEsLTJ9LHstMSwyfSx7LTEsLTJ9LAoJezIsMX0sezIsLTF9LHstMiwxfSx7LTIsLTF9Cn07CgoKaW50IGlzSW5SYW5nZShpbnQgeCwgaW50IHkpewoJaWYoKDAgPD0geCAmJiB4IDwgU0laRSkmJigwIDw9IHkgJiYgeSA8IFNJWkUpKXsKCQlyZXR1cm4gMTsKCX1lbHNlewoJCXJldHVybiAwOwoJfQp9Cgp2b2lkIHVwZGF0ZShpbnQgY3gsIGludCBjeSwgaW50IHR4LCBpbnQgdHkpewoJaWYoYm9hcmRbdHhdW3R5XSAhPSBJTkYgJiYgYm9hcmRbY3hdW2N5XSA+IGJvYXJkW3R4XVt0eV0gKyAxKXsKCQlib2FyZFtjeF1bY3ldID0gYm9hcmRbdHhdW3R5XSArIDE7Cgl9Cn0KCnZvaWQgcHJpbnRfYm9hcmQoKXsKCWludCBpLGo7CglwcmludGYoIi0tLS0tLS0gcHJpbnQgYm9hcmQgLS0tLS0tLVxuIik7Cglmb3IoaT0wOyBpIDwgU0laRTsgaSsrKXsKCQlmb3Ioaj0wOyBqIDwgU0laRTsgaisrKXsKCQkJaWYoYm9hcmRbaV1bal0gPT0gSU5GKXsKCQkJCXByaW50ZigiSU5GLCAiKTsKCQkJfWVsc2V7CgkJCQlwcmludGYgKCIlM2QsICIsIGJvYXJkW2ldW2pdKTsKCQkJfQoJCX0KCQlwcmludGYoIlxuIik7Cgl9CglwcmludGYoIi0tLS0tLS0gLS0tLS0gLS0tLS0gLS0tLS0tLVxuIik7Cn0KCnZvaWQgcHJpbnRfcm91dGUoaW50IFgsIGludCBZKXsKCglwcmludGYoIiAtLS0tIHJvdXRlIC0tLS0tXG4iKTsKCglpbnQgaSxqOwoJaW50IGxlbiA9IDE7CglpbnQgcm91dGVbU0laRV1bU0laRV07CgoJZm9yKGk9MDsgaSA8IFNJWkU7IGkrKyl7CgkJZm9yKGo9MDsgaiA8U0laRTsgaisrKXsKCQkJcm91dGVbaV1bal0gPSAwOwoJCX0KCX0KCglyb3V0ZVtYXVtZXSA9IGxlbjsKCgl3aGlsZSgxKXsKCQlpbnQgbWluWCwgbWluWTsKCQlpbnQgbWluID0gSU5GOwoJCWZvcihpPTA7IGkgPCA4OyBpKyspewoJCQlpZihpc0luUmFuZ2UoWCt3W2ldWzBdLCBZK3dbaV1bMV0pKXsKCQkJCWlmKG1pbiA+IGJvYXJkW1grd1tpXVswXV1bWSt3W2ldWzFdXSl7CgkJCQkJbWluWCA9IFggKyB3W2ldWzBdOwoJCQkJCW1pblkgPSBZICsgd1tpXVsxXTsKCQkJCQltaW4gPSBib2FyZFtYK3dbaV1bMF1dW1krd1tpXVsxXV07CgkJCQl9CgkJCX0KCQl9CgkJLy8gaW5jcmVzZSBwYXRoIHdhbGsgbGVuZ3RoCgkJbGVuKys7CgkJWCA9IG1pblg7CgkJWSA9IG1pblk7CgkJcm91dGVbWF1bWV0gPSBsZW47CgoJCWlmKG1pbiA9PSAwKXsKCQkJYnJlYWs7CgkJfQoJfS8qd2hpbGUqLwoKCglmb3IoaT0wOyBpIDwgU0laRTsgaSsrKXsKCQlmb3Ioaj0wOyBqIDxTSVpFOyBqKyspewoJCQkKCQkJaWYocm91dGVbaV1bal0gPT0gMCl7CgkJCQlwcmludGYoIiAgICwgIik7CgkJCX1lbHNlewoJCQkJcHJpbnRmKCIlM2QsICIsIHJvdXRlW2ldW2pdKTsKCQkJfQoJCX0KCQlwcmludGYoIlxuIik7Cgl9CgoKfQoKCgppbnQgZ2V0U2NvcmUoaW50IHN0YXJ0WCwgaW50IHN0YXJ0WSwgaW50IGVuZFgsIGludCBlbmRZKXsKCWludCBpLGosazsKCgkKCWlmKCFpc0luUmFuZ2Uoc3RhcnRYLCBzdGFydFkpKXsKCQlwcmludGYoIm91dCBvZiByYW5nZSFcbiIpOwoJCWV4aXQoMSk7CQoJfQoJaWYoIWlzSW5SYW5nZShlbmRYLCBlbmRZKSl7CgkJcHJpbnRmKCJvdXQgb2YgcmFuZ2UhXG4iKTsKCQlleGl0KDEpOwkKCX0KCgkvLyBpbml0aWFsaXplIGJvYXJkCglmb3IoaT0wOyBpIDwgU0laRTsgaSsrKXsKCQlmb3Ioaj0wOyBqIDwgU0laRTsgaisrKXsKCQkJYm9hcmRbaV1bal0gPSBJTkY7CgkJfQoJfQoJLy8gcmVjb3JkIG1pbmltdW0gY29zdAoJYm9hcmRbZW5kWF1bZW5kWV0gPSAwOwoKCXByaW50X2JvYXJkKCk7CgoJd2hpbGUoMSl7CgoJCWludCBpLGo7CgkJZm9yKGk9MDsgaSA8IFNJWkU7IGkrKyl7CgkJCWZvcihqPTA7IGogPCBTSVpFOyBqKyspewoJCQkJZm9yKGs9MDsgayA8IDg7IGsrKyl7CgkJCQkJaWYoaXNJblJhbmdlKGkrd1trXVswXSwgait3W2tdWzFdKSl7CgkJCQkJCXVwZGF0ZShpLGosaSt3W2tdWzBdLCBqK3dba11bMV0pOwoJCQkJCX0KCQkJCX0KCQkJfQoJCX0KCgkJcHJpbnRfYm9hcmQoKTsKCgkJaWYoYm9hcmRbc3RhcnRYXVtzdGFydFldICE9IElORil7CgkJCXByaW50ZigiLS0tLS0gZmluZCAhISAtLS0tLVxuIik7CgkJCXByaW50X3JvdXRlKHN0YXJ0WCwgc3RhcnRZKTsKCQkJYnJlYWs7CgkJfQoKCX0vKndoaWxlKi8KCglyZXR1cm4gYm9hcmRbc3RhcnRYXVtzdGFydFldOwp9CgoKCmludCBtYWluKGludCBhcmdjLCBjb25zdCBjaGFyICphcmd2W10pCnsKCglpbnQgc3RhcnRYPTEsIHN0YXJ0WT0xOwoJaW50IGVuZFg9NywgZW5kWT01OwoKCglnZXRTY29yZSgKCQlzdGFydFksc3RhcnRYLAoJCWVuZFksZW5kWAoJCSk7CgkKCXJldHVybiAwOwp9