/*******************************************************************
**author:LiangHong
**date:2008.6.11
**describe:pku2243
*******************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int used[50][50], x2, y2;
char a[3], b[3];
int d[8][2]={{-1,-2},{-1,2},{-2,1},{-2,-1},{2,1},{2,-1},{1,2},{1,-2}};
typedef struct {
    int x;
    int y;
    int moves;
}point;
point queue[10000];
void bfs(int x1,int y1);

int main(void)
{
    int  i, j, x1, y1, t;

    while (scanf("%s%s", a, b) != EOF) {
        for (i = 1; i <= 8; i++)
            for (j = 'a'-'a'; j <= 'h'-'a'; j++)
                used[i][j] = 1;
        memset(queue, 0, sizeof(point)*1000);
        x2 = b[0]-'a';
        y2 = b[1]-'1';
        x1 = a[0]-'a';
        y1 = a[1]-'1';
        if (x1 > x2) {
            t = x1;
            x1 = x2;
            x2 = t;
            t = y1;
            y1 = y2;
            y2 = t;
        }
        bfs(x1, y1);
    }
    return 0;

}

void bfs(int x1,int y1)
{
    int tx, ty, k, cx, cy, i;
    point temp;
    int head = 0, tail = 1;
    queue[0].x = x1;
    queue[0].y = y1;
    queue[0].moves = 0;
    i = 0;
    while(head < tail)
	{
		cx=queue[head].x;
		cy=queue[head].y;
		head++;
		if (cx == x2 && cy == y2) {
            break;
		}
		for(k = 0; k < 8; k++)
		{
			tx = cx + d[k][0];
			ty = cy + d[k][1];
			temp.x = tx;
			temp.y = ty;
			temp.moves = queue[i].moves+1;
			if(tx >= 0 && tx <= 8 && ty >= 'a'-'a' && ty <= 'h'-'a' && used[tx][ty])
			{
				queue[tail].x = temp.x;
				queue[tail].y = temp.y;
				queue[tail].moves = temp.moves;
				tail++;
				used[tx][ty] = 0;
			}
		}
		i++;
	}
	printf("To get from %s to %s takes %d knight moves.\n", a, b, queue[i].moves);
}

• Re:为什么h8 a1过不去？？从小数据到大数据能过，大数据到小数据过不去，大牛指点 (2060) cigaring 2010-11-29 18:33:52