首页 > ACM题库 > UVA > UVA 439-Knight Moves-简单BFS
2014
01-15

UVA 439-Knight Moves-简单BFS

UVA 439  Knight Moves

很简单的骑士周游问题,简单的BFS

一个骑士在当前位置的话可以像8个方向走,至于骑士是怎么走的可以百度一下

记录起点和终点的行列并算出它的标号(整个棋盘是8*8的,按行优先去编号从1到64,所以每个格子都会有一个唯一的编号)

走了8个方向记录下每个方向的编号,每得到一个编号就判断和终点编号是否相同,是的话就已经走到了,跳出,否则的话这个格子入队

另外就是记录步数,就是代码中的k

另外要注意判断起点和终点相同的情况,都是输出0

#include <stdio.h>
#include <string.h>
int d[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};

char a[3],b[3];
int num;
int x, y ,xx ,yy;
struct Q
{
    int x;
    int y;
    int bu;
} q[10005];
int vis[15][15];
void bfs(int x, int y)
{
    int head = 0;
    int rear = 1;
    q[head].x = x;
    q[head].y = y;
    for (int i = 0; i < 10005; i ++)
    {
	q[i].bu = 99999;
    }
    q[head].bu = 0;
    while (head < rear)
    {
	for (int i = 0; i < 8; i ++)
	{
	    if (q[head].x + d[i][0] == xx && q[head].y + d[i][1] == yy)
	    {
		num = q[head].bu + 1;
		return;
	    }
	    if (q[head].x + d[i][0] >= 1 && q[head].x + d[i][0] <= 8 && q[head].y + d[i][1] >= 1 && q[head].y + d[i][1] <= 8)
	    {
		q[rear].x = q[head].x + d[i][0];
		q[rear].y = q[head].y + d[i][1];
		q[rear].bu = q[head].bu + 1;
		rear ++;
	    }
	}
	head ++;
    }	
}
int main()
{
    while(scanf("%s%s", a, b) != EOF)
    {
	num = 0;
	memset(vis, 0, sizeof(vis));
	memset(q, 0, sizeof(q));
	x = a[0] - 'a' + 1;
	y = a[1] - '0';
	xx = b[0] - 'a' + 1;
	yy = b[1] - '0';
	bfs(x, y); 
	if (x == xx && y == yy)
	    num = 0;
	printf("To get from %s to %s takes %d knight moves.\n",a,b, num);
    }
    return 0;
}

  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。