迷宫路径求解

计算机科学与技术专业《数据结构与算法》

课程设计报告

设计题目：迷宫路径求解专业：

学号：

姓名：

指导老师：

完成日期：

一、需求分析

迷宫路径求解：利用二维数组创建一个迷宫。编写一个算法能够完成输出走出迷宫的所有的路径。

二、设计概要

maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,1,1,1,1,0,0,0,1},

{1,0,0,0,0,1,0,0,1,0,1},

{1,0,1,1,0,1,0,1,1,0,1},

{1,0,0,1,0,0,0,1,0,0,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,0,0,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1,1}

};

一个迷宫用m*n的二维数组存储，用“0”代表可以通行，用“1”代表墙壁，不可通行。迷宫有一个路口和一个出口，设入口坐标为（x1，y1），出口坐标（x2，y2）。从迷宫的一个位置向东、南、西、北任意一个方向移动一步，前面若为“0”，则可前进一步，否则通行受阻，不能前进，则按顺时针改变为下一个方向。用一个switch语句控制方向的选择,

如：

switch(d)

{case 0:i=stack[s].i-1;j=stack[s].j;break; /*向西*/

case 1:i=stack[s].i;j=stack[s].j+1;break; /*向南*/

case 2:i=stack[s].i+1;j=stack[s].j;break; /*向东*/

case 3:i=stack[s].i;j=stack[s].j-1;break; /*向北*/

}

在走的同时需要用一个与迷宫同样大小的二维数组mark来存储走过的路径。避免重走已经走不通的老路。

为了寻找从入口点到出口点的一条通路，首先从入口点出发，按照四个方向的次序，当可以向前移动一步时，就把当前的的坐标入栈，若从当前位置无法继续前进时就做出栈操作，从上一次的位置的下一个方向，向前试探前进。如果当前位置为出口时，则表明找到一条路径从入口到出口的路径，打印出路径。若做出栈时为空，且当前位置不是出口，则表明没有找到一条可以出去的路径。结束程序。

三、详细设计

1.数据类型的定义；

struct BinTreeNode

{ int i;

int j;

int d;

}path[maxsize],stack[maxsize];

2.初始化迷宫：

maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,1,1,1,1,0,0,0,1},

{1,0,0,0,0,1,0,0,1,0,1},

{1,0,1,1,0,1,0,1,1,0,1},

{1,0,0,1,0,0,0,1,0,0,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,0,0,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1,1}

};

3.迷宫路径求解函数

void mazeframe(int x1,int y1,int x2,int y2)

{int i,j,d,find,k,n,m;

s++;

stack[s].i=x1;

stack[s].j=y1;

stack[s].d=-1;

maze[x1][y1]=-1;

while(s>-1)

{i=stack[s].i;

j=stack[s].j;

d=stack[s].d;

if(i==x2 && j==y2)

{printf("Path NO.%d:",count++); 打印可以走通的路径；

printf("\n");

for(k=0;k<=s;k++)

{printf("(%d,%d)->",stack[k].i,stack[k].j);

if((k+1)%5==0) printf("\n");

}

printf("\n");

printf("Press any key to contiune....\n");

getch();

printf("\n");

if(s+1

{for(k=0;k<=s;k++)

path[k]=stack[k];

minlen=s+1;

}

maze[stack[s].i][stack[s].j]=0;

i=stack[s].i;

j=stack[s].j;

d=stack[s].d;

}

find=0;

while(d<4 && find==0)

{d++;

switch(d)

{case 0:i=stack[s].i-1;j=stack[s].j;break; 东、南、西、北等方向的选择；

case 1:i=stack[s].i;j=stack[s].j+1;break;

case 2:i=stack[s].i+1;j=stack[s].j;break;

case 3:i=stack[s].i;j=stack[s].j-1;break;

}

if(maze[i][j]==0&&maze[i][j]!=-1) find=1;

}

if(find==1)

{stack[s].d=d;

s++;

stack[s].i=i;

stack[s].j=j;

stack[s].d=-1;

maze[i][j]=-1;

}

else

{maze[stack[s].i][stack[s].j]=0;

s--;

}

}

printf("short path:");

printf("\n");

for(k=0;k

{printf("(%d,%d)->",path[k].i,path[k].j);

if((k+1)%5==0) printf("\n");

}

printf("\n");

}

四、调试分析

迷宫路径的求解，重点在于走过的点的存储和还原，程序在调试的过程中出现不能正确的输出路径，还有不能输出所有的路径。后发现在循环控制出现了问题。改进后所有问基本得到解决。

五、用户手册

由于迷宫是由二维数组定义的，数据输入量大，不利于程序的调试和用户的使用。因此本程序对迷宫的二维数组进行了初始化，所以不需要用户输入迷宫的二维数组。

用户只需根据提示操作就可以得到所有迷宫的路径。

1.本程序是在window XP下，用win-tc编写调试和运行的。

2.运行程序，首先会看到用户欢迎界面！看见程序的名称、制作者、制作日期等信息。

根据提示：Press any key to continue….(按任意键继续……)

六、测试结果

使用前面的二维数组，迷宫见设计概要的图。

结果如下：

第一条路径：（1，1）->（2，1）->（2，2）->（2，3）->（2，4）->（3，4）->（4，4）->（4，5）->（4，6）->（3，6）->（2，6）->（2，7）->（1，7）->（1，8）->（1，9）->（2，9）->（3，9）->（4，9）->（4，8）->（5，8）->（6，8）->（7，8）->（7，9）

第二条路径：（1，1）->（2，1）->（2，2）->（2，3）->（2，4）->（3，4）->（4，4）->->（4，5）->（4，6）->（5，6）->（6，6）->（7，6）->（7，7）->（7，8）->（7，9）

第三条路径：（1，1）->（2，1）->（3，1）->（4，1）->（4，2）->（5，2）->（6，2）->（7，2）->（7，3）->（7，4）->（7，5）->（7，6）->（6，6）->（5，6）->（4，6）->（3，6）->（2，6）->（2，7）->（1，7）->（1，8）->（1，9）->（2，9）->（3，9）->（4，9）->（4，8）->（5，8）->（6，8）->（7，8）->（7，9）

第四条路径：（1，1）->（2，1）->（3，1）->（4，1）->（4，2）->（5，2）->（6，2）->（7，2）->（7，3）->（7，4）->（7，5）->（7，6）->（7，7）->（7，8）->（7，9）

最短路径：（1，1）->（2，1）->（3，1）->（4，1）->（4，2）->（5，2）->（6，2）->（7，2）->（7，3）->（7，4）->（7，5）->（7，6）->（7，7）->（7，8）->（7，9）

七、心得体会

1.在整个程序的编写过程中，了解到栈，队列这两种存储结构对于一个程序的重要性。利

用还栈和队列可以使程序完成复杂的算法。

2.栈和队列可以和递归函数之间进行互换。利用栈可以写出非递归函数，增强函数的可读

性。

八．附录

源代码：

#include

#include

#include

#define NULL 0

#define maxsize 100

struct BinTreeNode

{ int i; int j; int d;

}path[maxsize],stack[maxsize];

int maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,1,1,1,1,0,0,0,1},

{1,0,0,0,0,1,0,0,1,0,1},

{1,0,1,1,0,1,0,1,1,0,1},

{1,0,0,1,0,0,0,1,0,0,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,1,1,1,0,1,0,1,1},

{1,1,0,0,0,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1,1}

};

int s=-1;

int count=1;

int minlen=maxsize;

void mazeframe(int x1,int y1,int x2,int y2)

{int i,j,d,find,k,n,m;

s++;

stack[s].i=x1;

stack[s].j=y1;

stack[s].d=-1;

maze[x1][y1]=-1;

while(s>-1)

{i=stack[s].i;

j=stack[s].j;

d=stack[s].d;

if(i==x2 && j==y2)

{printf("Path NO.%d:",count++);

printf("\n");

for(k=0;k<=s;k++)

{printf("(%d,%d)->",stack[k].i,stack[k].j);

if((k+1)%5==0) printf("\n"); }

printf("\n");

printf("Press any key to contiune....\n");

getch();

printf("\n");

if(s+1

{for(k=0;k<=s;k++)

path[k]=stack[k];

minlen=s+1; }

maze[stack[s].i][stack[s].j]=0;

i=stack[s].i;

j=stack[s].j;

d=stack[s].d;

}

find=0;

while(d<4 && find==0)

{d++;

switch(d)

{case 0:i=stack[s].i-1;j=stack[s].j;break;

case 1:i=stack[s].i;j=stack[s].j+1;break;

case 2:i=stack[s].i+1;j=stack[s].j;break;

case 3:i=stack[s].i;j=stack[s].j-1;break; } if(maze[i][j]==0&&maze[i][j]!=-1) find=1;

}

if(find==1)

{stack[s].d=d;

s++;

stack[s].i=i;

stack[s].j=j;

stack[s].d=-1;

maze[i][j]=-1;

}

else

{maze[stack[s].i][stack[s].j]=0;

s--; }

}

printf("short path:");

printf("\n");

for(k=0;k

{printf("(%d,%d)->",path[k].i,path[k].j);

if((k+1)%5==0) printf("\n");

}

printf("\n");

}

/*程序进入界面*/

void print2()

{int i,j,k;

for(i=0;i<=79;i++)

{printf("*");}

for(i=0;i<=15;i++)

{printf("*");

for(j=0;j<=77;j++)

{printf(" ");}

printf("*");

if(i==3)

{printf("*");

for(k=0;k<=17;k++)

{printf(" ");}

printf("Curriculum Project ");

for(k=0;k<=17;k++)

{printf(" ");}

printf("*");}

if(i==4)

{printf("*");

for(k=0;k<=17;k++)

{printf(" ");}

printf("Computer science and technical specialty ");

for(k=0;k<=18;k++)

{printf(" ");}

printf("*");}

if(i==2)

{printf("*");;

for(k=0;k<=25;k++)

{printf(" "); }

printf("All MazeFame Path Solution!");

for(k=0;k<=24;k++)

{printf(" ");}

printf("*");}

if(i==11)

{printf("*");

for(k=0;k<=24;k++)

{printf(" ");}

printf("Press any key to contiune....");

for(k=0;k<=23;k++)

{printf(" ");}

printf("*")}

if(i==14)

{printf("*");

for(k=0;k<=35;k++)

{printf(" ");}

printf("Elias made in 2008.1.08 Edition: 1.08! ");

for(k=0;k<=2;k++)

{printf(" ");}

printf("*");}}

for(i=0;i<=79;i++)

{printf("*");}

}

/*主函数*/

main()

{ int i,j;

print2();

getch();

clrscr();

printf("Primitive Labyrinth Chart!\n");

for(i=0;i<=8;i++)

{for(j=0;j<=10;j++)

{printf("%d",maze[i][j]); }

printf("\n");}

printf("Press any key to contiune....\n");

getch();

mazeframe(1,1,7,9);

getch();

}

算法分析与设计 查找迷宫的最短路径(深度算法)

算法分析与设计 查找迷宫的最短路径(深度算法) 计算机科学与技术12级 16班 2012/12/16

【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。 【关键词】:最短路径; 时间复杂度;深度优先搜索 【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal . 【Key phrase】Shortest path ; time complexity ; deep-first search

迷宫最短路径数据结构源码实验报告

实验报告 课程名称数据结构 实验名称迷宫最短路径 实验类型综合型 实验地点计405机房 实验日期2017.5.13 指导教师魏海平 专业软件工程 班级软件1601 学号1611030102 姓名寇春雷 辽宁石油化工大学计算机与通信工程学院

数据结构实验报告评分表

实验二迷宫最短路径 题目：迷宫最短路径 ⒈问题描述 从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1..m，1..n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。 ⒉基本要求 (1)输入数据 a.输入迷宫的大小m行和n列，两者为整数 b.由随机数产生0或1，建立迷宫。 (2)输出数据 首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，……，(i，j)，……，(1，1) 如无通道，则打印： THERE IS NO PATH. ⒊实现提示 (1)数据结构 ①为了在程序中判断方便，把迷宫扩展成为MAZE(0..m+1，0..n+1)，扩展部分的元素 设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。 ②用二维数组MOVE(1..8，1..2)存放八个方向上的位置量，如图所示： (i+MOVE[1，1]，j+MOVE[1，2]) ，2]) ，2]) ，2])

③为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻 找路径的过程中，若通过了位置（i，j），则将MARK（i，j）置为为1。 ④为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组， 对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置i和j，Q(P，2)记下其出发点在Q数组中的下标。 （2）算法基本思想 将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。 具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(i，j)=0 且MARK(i，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。 4.需求分析 (1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0=

迷宫问题的求解

迷宫问题求解 一．问题描述： 请设计一个算法实现迷宫问题求解。 二．需求分析： 程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户输入迷宫的大小与形态，以“0”表示墙壁，以“1”表示通路。利用栈操作寻找一条从入口至出口的通路，最终输出带有路线的迷宫。 三．算法思想： 1.栈的设计： 用计算机解迷宫问题时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通则继续向前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，可以利用“栈”来求解迷宫问题。 2. 表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中0表示墙壁（不通），1表示通路，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为0。这样做可使问题简化，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 3 0 1 1 1 1 1 1 1 0 0 4 0 1 1 0 0 1 0 0 0 0 5 0 0 1 1 1 0 1 1 1 0 6 0 1 0 0 1 1 1 1 1 0 7 0 0 0 0 0 0 0 0 0 0 3. 试探方向： 在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，

数据结构课程设计-迷宫问题的操作要点

1、课程设计目的 为了配合《数据结构》课程的开设，通过设计一完整的程序，掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法特进行题目为两个链表合并的课程设计。通过此次课程设计充分锻炼有关数据结构中链表的创建、合并等方法以及怎样通过转化成C语言在微机上运行实现等其他方面的能力。 2．课程设计的内容与要求 2.1问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图A 2.2设计要求： 要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。

3.2 概要设计 1.①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 ②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值 ③构建一个队列用于存储迷宫路径 ④建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况 ⑤实现搜索算法 ⑥屏幕上显示操作菜单 2.本程序包含10个函数： (1)主函数main() (2)手动生成迷宫函数shoudong_maze()

数据结构迷宫问题实验报告

《数据结构与算法设计》迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航

一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元

StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障 碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上 的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块 a、主程序模块

c语言实现迷宫最优路径选择

中国计量学院实验报告 实验课程：算法与数据结构实验名称：迷宫的最优路径班级：学号： 姓名：实验日期：2013-5-20 一．实验题目： 输入一迷宫 查找并输出迷宫的最优路径 实验成绩：指导教师：

二．算法说明 1.定义一个结构体来表示起点和末点的坐标,定义一个数组来存放迷宫. struct elem { int x;//行 int y;//列 }; //定义结构体 int M[10][10]; 2.给数组中空白处赋上从起点到该处步骤的值. int find(int n) { for(i=0;i<9;i++) for(j=0;j<10;j++) { if(M[i][j]==n) { {if (M[i][j+1]==0) M[i][j+1]=n+1; else if(M[i][j+1]>n+1) M[i][j+1]=n+1;} {if (M[i+1][j]==0) M[i+1][j]=n+1; else if(M[i+1][j]>n+1) M[i+1][j]=n+1;} {if (M[i][j-1]==0) M[i][j-1]=n+1; else if(M[i][j-1]>n+1) M[i][j-1]=n+1;} {if (M[i-1][j]==0) M[i-1][j]=n+1; else if(M[i-1][j]>n+1) M[i-1][j]=n+1;} } } } 3.给最优路径附上特定的值,方便最后的输出. for (;;) { if(M[q.x+1][q.y]==(n-1)) {q.x++;M[q.x][q.y]=0;} else {if(M[q.x][q.y-1]==(n-1)) {q.y--;M[q.x][q.y]=0;} else {if(M[q.x-1][q.y]==(n-1)) {q.x--;M[q.x][q.y]=0;} else if(M[q.x][q.y+1]==(n-1)) {q.y++;M[q.x][q.y]=0;}}} n--; if(e.x==q.x&&e.y==q.y) {M[e.x][e.y]=0; break;} }

实验四：A星算法求解迷宫问题实验

实验四：A*算法求解迷宫问题实验 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解迷宫问题，理解求解流程和搜索顺序。 二、实验内容 迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示点不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格(可以通过的)，最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的4个单元格(如果位于底边，则只有3个；位于4个角上，则只有2个是否能通过)。 A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。 A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n）其中：n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初

始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。 这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为：h（n）<=h（n）* 迷宫走的时候只能往上下左右走，每走一步，代价为1，这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：h（n）=|end.x –n.x|+ |end.y –n.y| 这里end表示迷宫的目标点，n表示当前点，很明显这里h（n）<=h（n）*。 g（n）容易表示，即每走一步的代价是1，所以利用f（n）=g（n）+h（n）这种策略，我们可以不断地逼近目标点，从而找到问题的解。 时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n). 实验结果：

迷宫路径求解

计算机科学与技术专业《数据结构与算法》 课程设计报告 设计题目：迷宫路径求解专业： 学号： 姓名： 指导老师： 完成日期：

一、需求分析 迷宫路径求解：利用二维数组创建一个迷宫。编写一个算法能够完成输出走出迷宫的所有的路径。 二、设计概要 maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,0,0,0,1}, {1,0,0,0,0,1,0,0,1,0,1}, {1,0,1,1,0,1,0,1,1,0,1}, {1,0,0,1,0,0,0,1,0,0,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1} }; 一个迷宫用m*n的二维数组存储，用“0”代表可以通行，用“1”代表墙壁，不可通行。迷宫有一个路口和一个出口，设入口坐标为（x1，y1），出口坐标（x2，y2）。从迷宫的一个位置向东、南、西、北任意一个方向移动一步，前面若为“0”，则可前进一步，否则通行受阻，不能前进，则按顺时针改变为下一个方向。用一个switch语句控制方向的选择, 如： switch(d) {case 0:i=stack[s].i-1;j=stack[s].j;break; /*向西*/ case 1:i=stack[s].i;j=stack[s].j+1;break; /*向南*/ case 2:i=stack[s].i+1;j=stack[s].j;break; /*向东*/ case 3:i=stack[s].i;j=stack[s].j-1;break; /*向北*/ } 在走的同时需要用一个与迷宫同样大小的二维数组mark来存储走过的路径。避免重走已经走不通的老路。 为了寻找从入口点到出口点的一条通路，首先从入口点出发，按照四个方向的次序，当可以向前移动一步时，就把当前的的坐标入栈，若从当前位置无法继续前进时就做出栈操作，从上一次的位置的下一个方向，向前试探前进。如果当前位置为出口时，则表明找到一条路径从入口到出口的路径，打印出路径。若做出栈时为空，且当前位置不是出口，则表明没有找到一条可以出去的路径。结束程序。 三、详细设计 1.数据类型的定义； struct BinTreeNode { int i; int j; int d;

数据结构迷宫问题课程设计

数据结构课程设计报告 设计题目：迷宫问题数据结构课程设计_ 班级：计科152 学号：19215225 姓名：徐昌港 南京农业大学计算机系

数据结构课程设计报告内容 一．课程设计题目 迷宫问题 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 二．算法设计思想 1.需求分析 （1）迷宫数据用一个二维数组int maze[row][col]来存储，在定义了迷宫的行列数后，用两个for循环来录入迷宫数据，并在迷宫周围加墙壁。 （2）迷宫的入口位置和出口位置可以由用户自己决定。 2.概要设计 （1）主程序模块： void main() { int maze[row][col]; struct mark start,end; //出入口的坐标 int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //方向，依次是东西南北 built_maze(maze); printf("请输入入口的横纵坐标："); scanf("%d,%d",&start.a,&start.b); printf("请输入出口的横纵坐标：");

scanf("%d,%d",&end.a,&end.b); printf("0为东，1为南，2为西，3为北，-1为出路\n"); maze_path(maze,dir,start,end); getchar(); } （2）栈模块——实现栈抽象数据类型 （3）迷宫模块——实现迷宫抽象数据类型，建立迷宫，找出迷宫的一条通路 3.详细设计 （1）坐标位置类型 struct mark{ int a,b; //迷宫a行b列为位置 }; （2）迷宫类型 void built_maze(int maze[row][col]) //按照用户输入的row行和col列的二维数组（元素值为0和1） //设置迷宫maze的初值，包括边上边缘一圈的值 void maze_path(int maze[row][col],int dir[4][2],struct mark start,struct mark end) //求解迷宫maze中，从入口start到出口end的一条路径， //若存在，则返回TRUE；否则返回FALSE （3）栈类型 struct element{ int i,j,d; //坐标与方向 }; typedef struct Linkstack{ element elem;

迷宫问题求解

课程设计报告 课题名称：迷宫问题的求解及演示姓名： 学号： 专业：计算机与信息学院 班级： 指导教师：

数据结构课程设计任务书针对本课程设计，完成以下课程设计任务书： 1.熟悉系统实现工具和上机环境。 2.根据课程设计任务，查阅相关资料。 3.针对所选课题完成以下工作： （1）需求分析 （2）概要设计 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4.书写上述文档和撰写课程设计报告

目录 第一部分课程设计任务书 (1) 第二部分课程设计报告 (2) 第一章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 需求分析 (4) 第二章课程设计总体方案及分析 (4) 3.1 概要设计 (7) 3.2 详细设计 (7) 3.3 调试分析 (10) 3.4 测试结果 (10) 第三章设计总结 (13) 4.1课程设计总结 (13) 4.2参考文献………………………………………………… 4.3 附录(源代码) (14)

第二部分课程设计报告 第一章课程设计内容和要求 2.1问题描述： 迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序，求出一条从入口到出口的路径并显示之（结果若能用C的绘图函数显示更好） 2.2需求分析： 1．要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 2.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 3.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。

数据结构课程设计-迷宫问题(参考资料)

目录第一部分需求分析 第二部分详细设计 第三部分调试分析 第四部分用户手册 第五部分测试结果 第六部分附录 第七部分参考文献

一、需求分析 1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。 2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j， d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 二、详细设计 1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路

退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。 3、所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。 显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。 4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的

迷宫-最短路径及所有路径的问题

#include using namespace std; #define MAXSIZE 200 #define m 999 #define n 999 typedef struct { int i,j,di; }Queue; Queue Stack[MAXSIZE],Path[MAXSIZE];//栈和存放最短路径长度的数组 int top=-1,count=1,minlen=MAXSIZE;//栈顶指针，路径计数器，最短路径长度 const int move[4][2]={ {-1,0},{0,1},{1,0},{0,-1}}; int mark[m][n]; //标志数组 int maze[m][n]; //迷宫数组 int i1=1,j1=1,i2=10,j2=10,m1=11,n1=11; //入口，出口坐标，迷宫大小 void Init_maze(); //初始化系统自带迷宫 void NewCreat(); //新建迷宫 void Put_in(); //输入进出口

void PutOut_all(); //找所有路径和最短路径并输出所有路径 void PutOut_Grap(); //输出迷宫图形 void Migong(); //使用迷宫 void main() { cout<<"*******************欢迎使用迷宫系统 *******************\n"; while(1) { int i; cout<<"请选择你要的操作：\n" <<"1.使用系统自带迷宫\n" <<"2.使用新建迷宫\n" <<"0.退出\n"; cout<<"请输入："; cin>>i; switch(i) { case 1: Init_maze();Migong();break; case 2: NewCreat();Migong();break; case 0: return;

数据结构试验——迷宫问题

数据结构试验——迷宫问题 （一）基本问题 1.问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清晰，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 2.数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈

int top=-1 //初始化栈 3设计运算算法 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。 （1）下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为—1），在栈不空时循环——取栈顶方块（不退栈）①若该方块为出口，输出所有的方块即为路径，其代码和相应解释如下：

求迷宫中从入口到出口的路径的算法及实现概要

求迷宫中从入口到出口的 路径的算法及实现 涂海丽东华理工大学３４４０００ １．本次设计所用到的库函数有：输入输出函数（ｓｔｄｉｏ．ｈ）过程调用函数（ｐｒｏｃｅｓｓ．ｈ）动态存储分配函数（ｍａｌｌｏｃ．ｈ）。 ２．本程序的设计过程分三大块：主程序（ｍａｉｎ（））试探函数（ｓｅａｒｃｈ（））数据子文件（ｉｎｐｕｔ．ｃ）。主要过程就是：通过主程序调用数据文件，然后用一维数组来模拟二维数组进行动态存储，再从第一个入口开始，调用试探函数探测通路，把探测到的通路入栈，进入下一层调用。直到找出所有的通路，最后打印输出。 ｆｏｒ（ｉ＝－１ｉ＜＝１＋＋ｉ）／／在当前点的８各方向进行探测 ｆｏｒ（ｊ＝－１ｊ＜＝１＋＋ｊ）｛ｉｈ＝ｉ０＋ｉｊｈ＝ｊ０＋ｊｉｆ（（ｉ！＝０｜｜ｊ！＝０）ｉｈ＞＝０ｉｈ＜ｒｏｗ＆ｊｈ＞＝０ｊｈ＜ｃｏｌｔａｂ［ｉｈ］［ｊｈ］＝＝０） ｛／／判断条件ｉｅ１［ｉｒ］＝ｉｈ／／当前点入栈，进入下一层调用 ｉｅ２［ｉｒ］＝ｊｈｔａｂ［ｉｈ］［ｊｈ］＝１ｓｅａｒｃｈ（ｒｏｗ，ｃｏｌ，ｔａｂ，ｉｈ，ｊｈ，ｉｒ＋１，ｉｅ１，ｉｅ２，ｎｏ）ｔａｂ［ｉ

ｈ］［ｊｈ］＝０｝｝｝ｍａｉｎ（）｛ＦＩＬＥ＊ｆｐｉｎｔｒｏｗ，ｃｏｌ，＊ｔａｂ１，＊＊ｔａｂ２，＊ｉｅ１，＊ｉｅ２，ｉｒ，ｎｏ，ｉ０，ｊ０，ｉ，ｊｉｆ（（ｆｐ＝ｆｏｐｅｎ（＂ｉｎｐｕｔ．ｃ＂，＂ｒ＂））＝＝ＮＵＬＬ）／／打开数据文件 ｛ｐｒｉｎｔｆ（＂ＴｈｅｏｐｅｎＥｒｒｏｒ！＂）ｅｘｉｔ（０）｝ｆｓｃａｎｆ（ｆｐ，＂％ｄ％ｄ＂，ｒｏｗ，ｃｏｌ）／／读入迷宫的矩阵行和列大小 ｔａｂ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ））／／申请动态存储区 ｔａｂ２＝（ｉｎｔ＊＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ＊））／／ｔａｂ１一维数组来模拟ｔａｂ２二维 数组ｉｅ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｉｅ２＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；ｉ＋＋）ｔａｂ２［ｉ］＝（ｔａｂ１［ｉ＊ｃｏｌ］）ｉ０＝０ｊ０＝０／／从入口（１，１）开始ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；＋＋ｉ）ｆｏｒ（ｊ＝０ｊ＜ｃｏｌ＋＋ｊ）ｆｓｃａｎｆ（ｆｐ，＂％ｄ＂，（ｔａｂ２［ｉ］［ｊ］））／／读入矩阵的内容 ｆｃｌｏｓｅ（ｆｐ）／／存入到ｔａｂ１中 三详细设计程序 ＃ｉｎｃｌｕｄｅ＜ｍａｌｌｏｃ．ｈ＞ ＃ｉｎｃｌｕｄｅ＜ｓｔｄｉｏ．ｈ＞＃ｉｎｃｌｕｄｅ＜ｐｒｏｃｅｓｓ．ｈ＞ｖｏｉｄｓｅａｒｃｈ（ｉｎｔｒｏｗ，ｉｎｔｃｏｌ，ｉｎｔ＊＊ｔａｂ，ｉｎｔｉ０，ｉｎｔｊ０，ｉｎｔｉｒ，ｉｎｔ＊ｉｅ１，ｉｎｔ＊ｉｅ２，ｉｎｔ＊ｎｏ）／／试探函数 ｛ｉｎｔｉ，ｊｈ，ｉｈ，ｊ，ｃｏｕｎｔｉｆ（ｉ０＝＝ｒｏｗ－１ｊ０＝＝ｃｏｌ－１）／／若能到达出口 ｛＋＋（＊ｎｏ）／／方法数加１ ｐｒｉｎｔｆ（＂＃－－－－－－－－－－－－－－－－Ｔｈｅ￣￣￣￣［％ｄ］ｔｈ￣￣￣￣￣Ｓｏｌｕｔｉｏｎ－－－－－－－－－－－－－－－－－－－－＃＼ｎ＂，＊ｎｏ）／／打印该种路径的出现顺序 ｐｒｉｎｔｆ（＂（％ｄ，％ｄ）＂，１，１）／／从入口开始打印 ｃｏｕｎｔ＝０／／输出换行计数

数据结构实验-迷宫问题汇总

实验报告 实验课名称：数据结构实验 实验名称：迷宫问题 班级：20130613 学号：16 姓名：施洋时间：2015-5-18 一、问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 二、数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号

int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 三、算法设计 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。

求解迷宫问题

求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1},

{1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c语言描述如下：

void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /*栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,输出路径*/ { printf("迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); }

数据结构迷宫问题的C 代码

数据结构课程设计——迷宫问题求解代码 问题描述及要求： 迷宫问题求解 输入： 第一行n，m表示迷宫大小n*m 之后有n行m列，全由01组成，0表示路，1表示墙 入口设为(0,0) 出口设为(n-1,m-1) 输出： 输出从入口到出口的所有不同解，每组解的第一行打印一个数表示第几组解，之后k行表示路径，如： 1 (0,0) (0,1) (1,1) 代码部分（已测试，可直接运行）： #include #include #define N255 int n,m,cnt; int maze[N][N],step[N][N]; struct Point{ int x,y; }path[N*N]; int oper[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; bool isvaild(int x,int y){ if(x>=0&&x=0&&y

Point tmp; tmp.x=x+oper[i][0]; tmp.y=y+oper[i][1]; path[len]=tmp; step[tmp.x][tmp.y]=1; dfs(tmp.x,tmp.y,len+1); step[tmp.x][tmp.y]=0; } } void work(){ step[0][0]=1; Point cur; cur.x=0; cur.y=0; path[0]=cur; dfs(0,0,1); } int main(){ scanf("%d%d",&n,&m); for(int i=0;i