看iampolaris的迷宫问题讨论--(堆栈) 在上面挂了N天了，可惜只给出了算法思想，未能找出最短的路径，也没给出源程序。于是出于兴趣，写这篇文章，与大家探讨一下最短路径的算法。这可是我的第一篇文章，肤浅的很，希望大家指正！不确定对所有的迷宫否都正确，我测试的几个还是没问题的，如果发现什么问题告诉我sduboy@163.com
其实算法思想就是一句话：“用队列实现广度优先遍历”。第一次遍历到出口时就找到了最短路径，算法停止。 MazePos pre 用于保存路径，只记上一步的那一个点。最后只需从出口顺着 pre走回去即可。
核心部分如下：bool TravelMaze(Maze maze[][10],int x0,int y0,int x1,int y1)
{
Queue *q=InitQueue();
MazePos pos;
int entranceX=x0, entranceY=y0;
int exitX=x1, exitY=y1;
if(!q) exit(1);
if(maze[x0][y0].s==0)return false;
pos.x=x0;pos.y=y0;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0;
maze[x0][y0].visited=true;
EnQueue(q,pos);
while(!QueueEmpty(q) &&((x0!=x1)||(y0!=y1)))
{
//开始广度优先遍历
pos=GetFrontElem(q);
x0=pos.x; y0=pos.y;
//将与之相邻的且可以通过的所有节点入队（最多4个哦）
//可以写的更简洁一些，不过这样更好理解。
if(maze[x0+1][y0].s==1 && !maze[x0+1][y0].visited)
{ x0++; pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0-1;maze[x0][y0].pre.y=y0;}
if(maze[x0-1][y0].s==1 &&!maze[x0-1][y0].visited)
{ x0--;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0+1;maze[x0][y0].pre.y=y0;}
if (maze[x0][y0+1].s==1 &&!maze[x0][y0+1].visited)
{ y0++;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0-1;}
if(maze[x0][y0-1].s==1 &&!maze[x0][y0-1].visited)
{ y0--;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0+1;}
DeQueue(q,&pos); //这个pos要直接扔掉地
// system("pause");
}
if(((x0==x1)&&(y0==y1))) {
//打印路径，倒着的路径(懒的把他转过来 :)
printpass(maze,entranceX,entranceY,exitX,exitY);
return true;
}
else return false;
}
//=====================================
没什么可说的了，下面是完整的代码。其中迷宫初始化的部分是直接考的别人的，表示感谢。其他的都是我的了，呵呵。
最短路径可能不只一条，这里只找一条。dev c++ 4960 下通过编译
（另外请问如何在dev c++下单不调试程序，我怎么就是不会用呢。开始
debug后，按f7根本无任何反映，高手赐教：）
#include <stdlib.h>
#include <stdio.h>
#define ElemType MazePos
typedef struct MazePos0{
int x,y;
}MazePos;
typedef struct maze0{
int s;//pass or wall
MazePos pre;
bool visited;
}Maze;
typedef struct QueueNode{
ElemType data;
struct QueueNode *next;
}queuenode;
typedef struct queue{
struct QueueNode *front;
struct QueueNode *rear;
}Queue;
Maze maze[10][10];
//=============================================
Queue* InitQueue()
{
Queue *q=NULL;
if(!(q=(Queue*)malloc(sizeof(Queue)))) return NULL;
q->front=q->rear=NULL;
return q;
}
bool EnQueue(Queue *q,ElemType data)
{
QueueNode *qn=NULL,*temp=NULL;
if(!q)return false;
if(!(qn=(QueueNode*)malloc(sizeof(QueueNode)))) return false;
qn->data=data;
qn->next=NULL;
if(q->rear)//加入第一各节点时q->rear==NULL
q->rear->next=qn;
q->rear=qn;
if(!q->front)q->front=qn;//同上
return true;
}
bool DeQueue(Queue *q,ElemType *data)
{
QueueNode *qn=NULL;
if(q->front==NULL) return false;
qn=q->front;
q->front=q->front->next;
*data=qn->data;
free(qn);
return true;
}
ElemType GetFrontElem(Queue *q)
{
if(q) return q->front->data;
}
bool QueueEmpty(Queue *q)
{
if(!q->front) return true;
else return false;
}
int ElementsCounts(Queue *q)
{
int i=0;
QueueNode *temp;
temp=q->front;
while(temp){ i++;temp=temp->next;}
return i;
}
//======================
void InitMaze1(Maze maze[10][10])
{
maze[1][1].s=1; maze[1][2].s=1; maze[1][4].s=1;
maze[1][5].s=1; maze[1][6].s=1; maze[1][8].s=1;
maze[2][1].s=1; maze[2][2].s=1; maze[2][4].s=1;
maze[2][5].s=1; maze[2][6].s=1; maze[2][8].s=1;
maze[3][1].s=1; maze[3][2].s=1; maze[3][3].s=1;
maze[3][4].s=1; maze[3][7].s=1; maze[3][8].s=1;
maze[4][1].s=1; maze[4][5].s=1; maze[4][6].s=1;
maze[4][7].s=1; maze[4][8].s=1;
maze[5][1].s=1; maze[5][2].s=1; maze[5][3].s=1;
maze[5][5].s=1; maze[5][6].s=1; maze[5][7].s=1;
maze[5][8].s=1;
maze[6][1].s=1; maze[6][3].s=1; maze[6][4].s=1;
maze[6][5].s=1; maze[6][7].s=1; maze[6][8].s=1;
maze[7][1].s=1;
//maze[6][4].s=0;
maze[7][5].s=1; maze[8][1].s=1;
maze[7][8].s=1; maze[8][2].s=1; maze[8][3].s=1;
maze[8][4].s=1; maze[8][5].s=1; maze[8][6].s=1;
maze[8][7].s=1;
maze[8][8].s=1;
}
void InitMaze2(Maze maze[][10])
{
int i,j;
printf("\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
maze[i][j].visited=false;
maze[i][j].pre.x=0;
maze[i][j].pre.y=0;
}
printf("\n");
}
//for(i=1;i<9;i++)
// for(j=1;j<9;j++) maze[i][j].s=1;
}
void PrintMaze(Maze maze[][10])
{
int i,j;
printf("\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ",maze[i][j].s);
}
printf("\n");
}
}
//========================
void printpass(Maze maze[][10],int x0,int y0,int x1,int y1)
{ int x,y;
x=x1;y=y1;
while(!((x1==x0)&&(y1==y0)))
{
printf(" (%d,%d) ",x1,y1);
x=maze[x1][y1].pre.x;
y=maze[x1][y1].pre.y;
x1=x;y1=y;
system("pause");
}
printf(" (%d,%d) ",x0,y0);
}
//=========================
bool TravelMaze(Maze maze[][10],int x0,int y0,int x1,int y1)
{
Queue *q=InitQueue();
MazePos pos;
int entranceX=x0, entranceY=y0;
int exitX=x1, exitY=y1;
if(!q) exit(1);
if(maze[x0][y0].s==0)return false;
pos.x=x0;pos.y=y0;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0;
maze[x0][y0].visited=true;
EnQueue(q,pos);
while(!QueueEmpty(q) &&((x0!=x1)||(y0!=y1)))
{
pos=GetFrontElem(q);
x0=pos.x; y0=pos.y;
if(maze[x0+1][y0].s==1 && !maze[x0+1][y0].visited)
{ x0++; pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0-1;maze[x0][y0].pre.y=y0;}
if(maze[x0-1][y0].s==1 &&!maze[x0-1][y0].visited)
{ x0--;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0+1;maze[x0][y0].pre.y=y0;}
if (maze[x0][y0+1].s==1 &&!maze[x0][y0+1].visited)
{ y0++;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0-1;}
if(maze[x0][y0-1].s==1 &&!maze[x0][y0-1].visited)
{ y0--;pos.x=x0;pos.y=y0;EnQueue(q,pos);
maze[x0][y0].visited=true;
maze[x0][y0].pre.x=x0;maze[x0][y0].pre.y=y0+1;}
DeQueue(q,&pos);
// system("pause");
}
if(((x0==x1)&&(y0==y1))) {
printpass(maze,entranceX,entranceY,exitX,exitY);
return true;
}
else return false;
}
int main()
{
InitMaze1(maze);
InitMaze2(maze);
int entranceX=1, entranceY=1;
int exitX=8, exitY=8;
PrintMaze(maze);
if(!TravelMaze(maze,entranceX,entranceY,exitX,exitY))
printf("Sorry, no solution.");
system("pause");
return 0;
}
