求最短路徑，最直接的廣度優先搜索。
#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
小鼠標 閱讀(149)
評論(0) 編輯 收藏 引用