#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, zero;
    zero = 0;
    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 (strcmp(a, b) == 0)
            printf("To get from %s to %s takes %d knight moves.\n", a, b, zero);
        else
            bfs(x1, y1);
    }
    return 0;

}

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

• 有，不止有一，有好多 (71) MIRKING 2008-06-11 14:36:04
  • Re:有，不止有一，有好多 (99) 1152230301 2011-07-12 09:58:52
  • Re:有，不止有一，有好多 (20) 1152230301 2011-07-12 10:00:02