UC知道迷宫最短路径
来源：百度知道 编辑：UC知道 时间：2024/09/21 09:28:04
下面程序如何修改为最短路径？
#include "stdio.h"
#define StackSize 100
typedef struct{
int i,j;
}PosType;
typedef struct{
PosType pos;
int di;
} ElemType;
typedef struct {
ElemType elem[StackSize];
int top;
}SqStack;
InitStack(SqStack *pS)
{
pS->top=0; /* top指向栈顶的上一个元素 */
}
int Push(SqStack *pS,ElemType e)
{
if (pS->top==StackSize-1) /* 栈满 */
return 0;
pS->elem[pS->top]=e;
pS->top=pS->top+1;
return 1;
}
int Pop(SqStack *pS,ElemType* pe)
{
if (pS->top==0) /* 栈空 */
return 0;
pS->top = pS->top - 1;
*pe = pS->elem[pS->top];
return 1;
}
main()
{
SqStack S;
ElemType e;
PosType pos,pos_end;
int maze[10][10]={ /* 离散迷宫矩阵，0表示墙壁 */
{0,0,0,0,0,0,0,0,0,0},
#include "stdio.h"
#define StackSize 100
typedef struct{
int i,j;
}PosType;
typedef struct{
PosType pos;
int di;
} ElemType;
typedef struct {
ElemType elem[StackSize];
int top;
}SqStack;
InitStack(SqStack *pS)
{
pS->top=0; /* top指向栈顶的上一个元素 */
}
int Push(SqStack *pS,ElemType e)
{
if (pS->top==StackSize-1) /* 栈满 */
return 0;
pS->elem[pS->top]=e;
pS->top=pS->top+1;
return 1;
}
int Pop(SqStack *pS,ElemType* pe)
{
if (pS->top==0) /* 栈空 */
return 0;
pS->top = pS->top - 1;
*pe = pS->elem[pS->top];
return 1;
}
main()
{
SqStack S;
ElemType e;
PosType pos,pos_end;
int maze[10][10]={ /* 离散迷宫矩阵，0表示墙壁 */
{0,0,0,0,0,0,0,0,0,0},
用堆栈不一定能得出最短路径，改用队列可以实现最短路径，下面是《数据结构算法与应用-C++语言描述》里面的一段话。
[迷宫老鼠] 使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（ 1，2）和（2，1）置为1。
1 1 0
1 1 1
0 0 0
a）
1 1 1
1 1 1
0 0 0
b）
1 1 1
1 1 1
1 0 0
c）
节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有
（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置
为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将
会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，
1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随
后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，
节点（3，1）成为新的E-节点，将队列清空。节点（3，1）展开，（3，2）被加入队列中，而
（3，1）被删除。（3，2）变为新的E-节点，展开此节点后，到达节点（3，3），即迷宫的出口。
使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。