最直接的廣度優(yōu)先搜索題。求最短路一般用廣搜，廣搜要用到隊(duì)列；與廣搜對(duì)應(yīng)的是深搜，深搜要用到棧，它能找到所有路，這里不展開(kāi)說(shuō)了。剛?cè)腴T(mén)的同學(xué)可以先看看隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。
無(wú)論廣搜還是深搜，走過(guò)的節(jié)點(diǎn)一定要標(biāo)記，以免多次走過(guò)同一個(gè)節(jié)點(diǎn)。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100
typedef struct
{
int x;
int y;
int p;
}Node;
Node queue[LEN];
int r, f;
char mp[10][10];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void traceBack(int n)
{
if(n == -1)
return;
else
{
traceBack(queue[n].p);
printf("(%d, %d)\n", queue[n].x - 1, queue[n].y - 1);
}
}
int main()
{
int i, j;
int n = 5;
int amx = 5;
int amy = 5;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
scanf("%d", &mp[i][j]);
}
for(i = 0; i <= n + 1; i++)
{
mp[0][i] = mp[n + 1][i] = 1;
mp[i][0] = mp[i][n + 1] = 1;
}
f = 0;
queue[f].x = 1;
queue[f].y = 1;
queue[f].p = -1;
r = 1;
int find = 0;
while(f != r && find == 0)
{
int x = queue[f].x;
int y = queue[f].y;
f++;
for(i = 0; i < 4; i++)
{
int x1 = x + d[i][0];
int y1 = y + d[i][1];
if(mp[x1][y1] == 0)
{
queue[r].x = x1;
queue[r].y = y1;
queue[r].p = f - 1;
mp[x1][y1] = 1;
r++;
}
if(amx == x1 && amy == y1)
{
find = 1;
break;
}
}
}
traceBack(r - 1);
//system("pause");
}posted on 2012-08-02 19:51
小鼠標(biāo) 閱讀(225)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
圖論