[数据结构] 用堆栈实现迷宫求解问题

这个是偶今天实验课的作业。

基本思想:

若当前位置可以通过,则压入栈中,否则探求下一位置,若走不通,则回朔,迷宫大小:M*N.迷宫设置自定义。
求解迷宫问题的简单方法是:从入口出发,沿某一方向进行探索,若能走通,则继续向前走;否则沿原路返回,换一方向再进行探索,直到所有可能的通路都探索到为止。

为避免走回到已经进入的点(包括已在当前路径上的点和曾经在当前路径上的点),凡是进入过的点都应做上记号。

migong

求迷宫中一条从入口到出口的路径的算法可简单描述如下:
设定当前位置的初值为入口位置:
do
{
若当前位置可通,则
{
将当前位置插入堆栈顶;
若该位置是出口位置,则结束;
否则切换当前位置的东邻块为新的当前位置;
}
否则,
若堆栈不空且栈顶位置尚有其他方向未经探索; 则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相邻块;
若栈不空但栈顶位置的四周均不可通, 则
{
删去栈顶位置;
若栈不空,则重新测试新的栈顶位置,
直至找到一个可通的相邻或出栈至栈空;
}
}(栈不空)

代码:
gcc (GCC) 3.3.5 (Debian Linux 1:3.3.5-13) 下调试通过
C语言实现


#include “stdio.h”
#include “stdlib.h”
struct node
{
int row;
int col;
struct node *next;
};
struct node *p;
void push(int row,int col)
{
struct node *a;
a=(struct node *)malloc(sizeof(struct node));
a->row=row;
a->col=col;
a->next=p;
p=a;
}
void pop(void)
{
struct node *q;
q=p;
p=p->next;
free(q);
}
int main(void)
{
int row=1;
int col=1;
int a[8][11]={{1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,1,1,1,0,0,1},
{1,0,0,0,0,0,1,0,0,1,1},
{1,0,1,1,1,0,0,0,1,1,1},
{1,1,0,0,1,0,1,1,0,1,1},
{1,1,0,0,1,0,1,1,0,0,1},
{1,1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1},
};
/* struct node d;
p=&d; */
p=(struct node *)malloc(sizeof(struct node));
p->row=1;
p->col=1;
p->next=NULL;
/* push(row,col);
a[row][col]=1; */
while(row!=6||col!=9)
{
if(a[row][col+1]==0)
{
col=col+1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row-1][col]==0)
{
row=row-1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row][col-1]==0)
{
col=col-1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row+1][col]==0)
{
row=row+1;
push(row,col);
a[row][col]=1;
continue;
}
pop();
if(p->next==NULL)break;
row=p->row;
col=p->col;
}

if(row==6&&col==9)
{

while(p->next!=NULL)
{
printf(“%d %d\n”,p->row,p->col);
pop();
}
}
else printf(“No Answer !!!”);

return 0 ;
}

5 Responses to “[数据结构] 用堆栈实现迷宫求解问题”


Comments are currently closed.