最直接的广度优先搜索题。求最短路一般用广搜，广搜要用到队列；与广搜对应的是深搜，深搜要用到栈，它能找到所有路，这里不展开说了。刚入门的同学可以先看看队列这种数据结构。
无论广搜还是深搜，走过的节点一定要标记，以免多次走过同一个节点。
以下是本题代码：
#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
小鼠标 阅读(207)
评论(0) 编辑 收藏 引用 所属分类:
图论