题意：

输入两组坐标，输出骑士从一个到另一个最少要几步（骑士走日字）

要点：

标准的BFS题，寻找最短路径，用队列做

15170656

Accepted

176K

16MS

1099B

2016-02-17 17:36:15

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;bool visit[20][20];int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };struct node{	int x;	int y;	char c;	int num;};node a, b;queue
        
          que;int xx, yy;void bfs(){	que.push(a);	visit[a.x][a.y] = false;	while (!que.empty())		//直到所有的点都遍历过	{		node temp = que.front();		if (temp.x == b.x&&temp.y == b.y)		{			printf("To get from %c%d to %c%d takes %d knight moves.\n", a.c, a.y, b.c, b.y, temp.num);			return;		}		que.pop();		for (int i = 0; i < 8; i++)		{			node next;			xx = temp.x + dx[i];			yy = temp.y + dy[i];			if (!visit[xx][yy] || xx < 1 || xx > 8 || yy < 1 || yy > 8)//越界就跳过				continue;			next.x = xx;			next.y = yy;			next.num = temp.num + 1;			visit[xx][yy] = false;			que.push(next);		}	}}int main(){	while (~scanf("%c%d %c%d", &a.c, &a.y, &b.c, &b.y))	{		getchar();				//除去换行符		while (!que.empty())	//每次都要要清空队列			que.pop();		a.x = a.c - 'a' + 1;		b.x = b.c - 'a' + 1;		a.num = 0;		memset(visit, true, sizeof(visit));		bfs();	}	return 0;}