1440.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1440 on 2005-10-07 at 18:43:43 */ 
#include <cstdio>
#include <cstring>
#define  INFINIT  60000

int main()
{
	int step[8][8][8][8];
	int i, j, k, l, m, n;
	int a, b, c, d;
	char line[8];
	
	for(i = 0; i < 8; i++) {
		for(j = 0; j < 8; j++) {
			for(k = 0; k < 8; k++) {
				for(l = 0; l < 8; l++) {
					if(i == k && j == l) {
						step[i][j][k][l] = 0;
					} else if((i-k)*(j-l) == 2 || (i-k)*(j-l) == -2) {
						step[i][j][k][l] = 1;
					} else {
						step[i][j][k][l] = INFINIT;
					}
				}
			}
		}
	}
	for(m = 0; m < 8; m++) {
		for(n = 0; n < 8; n++) {
			for(i = 0; i < 8; i++) {
				for(j = 0; j < 8; j++) {
					for(k = 0; k < 8; k++) {
						for(l = 0; l < 8; l++) {
							if(step[i][j][m][n] + step[m][n][k][l] < 
								step[i][j][k][l]) {
								step[i][j][k][l] = step[i][j][m][n] + step[m][n][k][l];
							}
						}
					}
				}
			}
		}
	}
	while(gets(line) != NULL) {
		a = line[0] - 'a';
		b = line[1] - '1';
		c = line[3] - 'a';
		d = line[4] - '1';
		printf("To get from %c%c to %c%c takes %d knight moves.\n", 
		line[0], line[1], line[3], line[4], step[a][b][c][d]);
	}
	
	return 0;
}