pku1178.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 64
#define TheMax 10000

int D[SIZE][SIZE];
int Dis[4][2] = {{1, 2}, {1 ,-2}, {2, 1}, {2, -1}}; 
char s[130];
int p[64];

int In(int x, int y)
{
	return x >= 0 && x < 8 && y >= 0 && y < 8;
}

int Pos(int x, int y)
{
	return x * 8 + y;
}

int ABS(int x)
{
	return x > 0 ? x : -x;
}

int Max(int x, int y)
{
	return x > y ? x : y;
}

int King_Dis(int p1, int p2)
{
	int x1, x2, y1, y2, dx, dy;
	x1 = p1 / 8;
	y1 = p1 % 8;
	x2 = p2 / 8;
	y2 = p2 % 8;
	
	return Max(ABS(x1 - x2), ABS(y1 - y2));
}

void Flyod()
{
	int i, j, k;
	int x, y, nx, ny;
	for (i = 0; i < 64; i++)
	{
		for (j = 0; j < 64; j++)
		{
			D[i][j] = TheMax;
		}
	}
	for (i = 0; i < 64; i++)
	{
		D[i][i] = 0;
		x = i / 8;
		y = i % 8;
		for (j = 0; j < 4; j++)
		{
			nx = x + Dis[j][0];
			ny = y + Dis[j][1];
			if (!In(nx, ny))
			{
				continue;
			}
			D[Pos(x, y)][Pos(nx, ny)] = 1;
			D[Pos(nx, ny)][Pos(x, y)] = 1;
		}
	}
	for (k = 0; k < 64; k++)
	{
		for (i = 0; i < 64; i++)
		{
			for (j = 0; j < 64; j++)
			{
				if (D[i][j] > D[i][k] + D[k][j])
				{
					D[i][j] = D[i][k] + D[k][j];
				}
			}
		}
	}
}

void Solve()
{
	int i, j, k, l;
	int min, tmp, nok;
	l = strlen(s) / 2;
	for (i = 0; i < l; i++)
	{
		p[i] = Pos(s[i * 2] - 'A', s[i * 2 + 1] - '1');
	}
	min = TheMax;
	for (i = 0; i < 64; i++)
	{
		for (j = 1, nok = 0; j < l; j++)
		{
			nok += D[i][p[j]];
		}
		for (j = 1; j < l; j++)
		{
			for (k = 0; k < 64; k++)
			{
				tmp = nok - D[i][p[j]] + King_Dis(p[0], k) + D[p[j]][k] + D[k][i];
				if (tmp < min)
				{
					min = tmp;
				}
			}
		}
	}
	printf("%d\n", min);
}

int main()
{
	Flyod();
	while (scanf("%s", s) != -1)
	{
		Solve();
	}
	return 0;
}