求最短路径，最直接的广度优先搜索。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 12
#define QLEN 3000
typedef struct
{
char x;
char y;
}Node;
typedef struct
{
int f;
int r;
Node *q;
}Queue;
int main()
{
//printf("%d\n", sizeof(Node));
int i, j;
int mp[LEN][LEN];
int rl[LEN][LEN];//road length
char a[3], b[3];
Node bg, ed;//begin end
Node t;
Queue q;// make && init queue
q.q = (Node*)malloc(sizeof(Node) * QLEN);
while(scanf("%s%s", a, b) != EOF)
{
bg.x = a[0] - 'a' + 2;
bg.y = a[1] - '1' + 2;
ed.x = b[0] - 'a' + 2;
ed.y = b[1] - '1' + 2;
for(i = 0; i < LEN; i++)//init map
for(j = 0; j < LEN; j++)
mp[i][j] = 0;
for(i = 0; i < LEN; i++)
mp[0][i] = mp[1][i] = mp[LEN - 1][i] = mp[LEN - 2][i] = 1;
for(i = 1; i < LEN - 1; i++)
mp[i][0] = mp[i][1] = mp[i][LEN - 1] = mp[i][LEN - 2] = 1;
mp[bg.x][bg.y] = 1;
mp[ed.x][ed.y] = 2;
//
/**//*for(i = 0; i < LEN; i++)
{
for(j = 0; j < LEN; j++)
printf("%d",mp[i][j]);
putchar(10);
}
*/
q.f = q.r = 0;
for(i = 0; i < LEN; i++)//init road length
for(j = 0; j < LEN; j++)
rl[i][j] = 0;
q.q[q.r++] = bg;
//
//printf("bx = %d by = %d\n", bg.x, bg.y);
//printf("ex = %d ey = %d\n", ed.x, ed.y);
//printf("%s\n%s\n", a, b);
while(q.f != q.r && strcmp(a, b))
{
t = q.q[q.f];//t = front of queue
q.f = (q.f + 1) % QLEN;
if(mp[t.x - 2][t.y + 1] == 2)
{
rl[t.x - 2][t.y + 1] = rl[t.x][t.y] + 1;
break;//1
}
else if(mp[t.x - 2][t.y + 1] == 0)
{
rl[t.x - 2][t.y + 1] = rl[t.x][t.y] + 1;
mp[t.x - 2][t.y + 1] == 1;//change map
q.q[q.r].x = t.x - 2;//change queue
q.q[q.r].y = t.y + 1;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x - 1][t.y + 2] == 2)//2
{
rl[t.x - 1][t.y + 2] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x - 1][t.y + 2] == 0)
{
rl[t.x - 1][t.y + 2] = rl[t.x][t.y] + 1;
mp[t.x - 1][t.y + 2] == 1;//change map
q.q[q.r].x = t.x - 1;//change queue
q.q[q.r].y = t.y + 2;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x + 1][t.y + 2] == 2)//3
{
rl[t.x + 1][t.y + 2] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x + 1][t.y + 2] == 0)
{
rl[t.x + 1][t.y + 2] = rl[t.x][t.y] + 1;
mp[t.x + 1][t.y + 2] == 1;//change map
q.q[q.r].x = t.x + 1;//change queue
q.q[q.r].y = t.y + 2;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x + 2][t.y + 1] == 2)//4
{
rl[t.x + 2][t.y + 1] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x + 2][t.y + 1] == 0)
{
rl[t.x + 2][t.y + 1] = rl[t.x][t.y] + 1;
mp[t.x + 2][t.y + 1] == 1;//change map
q.q[q.r].x = t.x + 2;//change queue
q.q[q.r].y = t.y + 1;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x + 2][t.y - 1] == 2)//5
{
rl[t.x + 2][t.y - 1] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x + 2][t.y - 1] == 0)
{
rl[t.x + 2][t.y - 1] = rl[t.x][t.y] + 1;
mp[t.x + 2][t.y - 1] == 1;//change map
q.q[q.r].x = t.x + 2;//change queue
q.q[q.r].y = t.y - 1;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x + 1][t.y - 2] == 2)//6
{
rl[t.x + 1][t.y - 2] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x + 1][t.y - 2] == 0)
{
rl[t.x + 1][t.y - 2] = rl[t.x][t.y] + 1;
mp[t.x + 1][t.y - 2] == 1;//change map
q.q[q.r].x = t.x + 1;//change queue
q.q[q.r].y = t.y - 2;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x - 1][t.y - 2] == 2)//7
{
rl[t.x - 1][t.y - 2] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x - 1][t.y - 2] == 0)
{
rl[t.x - 1][t.y - 2] = rl[t.x][t.y] + 1;
mp[t.x - 1][t.y - 2] == 1;//change map
q.q[q.r].x = t.x - 1;//change queue
q.q[q.r].y = t.y - 2;
q.r = (q.r + 1) % QLEN;
}
if(mp[t.x - 2][t.y - 1] == 2)//8
{
rl[t.x - 2][t.y - 1] = rl[t.x][t.y] + 1;
break;
}
else if(mp[t.x - 2][t.y - 1] == 0)
{
rl[t.x - 2][t.y - 1] = rl[t.x][t.y] + 1;
mp[t.x - 2][t.y - 1] == 1;//change map
q.q[q.r].x = t.x - 2;//change queue
q.q[q.r].y = t.y - 1;
q.r = (q.r + 1) % QLEN;
}
}
printf("To get from %s to %s takes %d knight moves.\n", a, b, rl[ed.x][ed.y]);
}
}
不得不承认，明白一个算法与实现一个算法之间是有不小距离的，写代码的时候有很多的细节需要注意，这些细节是在算法层面上无法遇到的。比如在写这道题的时候，很清楚就是让求两点间的最短路径， 写出了代码却老是超内存，原来我的malloc（）函数写在了while里面，并且没有及时free。
关于搜索代码写法的技巧问题。我这里代码写了很长，但完全可以简化，因为我写了很多重复的代码（一个马可以朝着8个方向走），这些可以通过数组记录增量的方式用一个循环有效代替。通过这种方法还可以有效降低出错的可能，因为每个增量是很容易写错的。
posted on 2012-03-01 18:38
小鼠标 阅读(137)
评论(0) 编辑 收藏 引用