课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
的名称:迷宫的求解问题
1. 问题描述:迷宫只有两个门,一个叫做入口,另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁,对前进方向形成了多处障碍,在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题,即找出从入口到出口的路径。
2. 基本要求:
(1)首先建立一个
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示迷宫的数据结构;
(2)要有试探方向和栈的设计;
(3)不能重复到达某点,不能发生死循环;
3. 算法思想:
若当前位置可通,则纳入路径,继续前进;若当前位置不可通,则后退,换方向继续探索;若四周均无通路,则将当前位置从路径中删去。
4. 模块划分:
(1)int maze[n1][n2]是首先建立一个迷宫的矩阵,0为通路,1为不通。
(2)main()函数将初始化top[],使得所有的开始方向为左。
(3)采用回溯法不断地试探并且及时的纠正错误,使得能够找到正确的路径。
5.数据结构
(1)坐标点的结构定义如下:
typedef struct node
{
int x;
int y;
int c;
}linkstack;
(2)迷宫的数据结构定义如下:
maze[m][n]
maze[i][j]=0 通路
maze[i][j]=1 不通
6. 源程序:
#include
#include
#define n1 10
#define n2 10
typedef struct node
{
int x;//存x坐标
int y;//存y坐标
int c;//存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右
}linkstack;
linkstack top[100];
//迷宫矩阵
int maze[n1][n2]={
1,1,1,1,1,1,1,1,1,1,
0,0,0,1,0,0,0,1,0,1,
1,1,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,0,
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,
};
int i,j,k,m=0;
main()
{//初始化top[],置所有方向数向左
for(i=0;i",top[j].x,top[j].y);}
printf("\n");
//打印选出路径的迷宫
for(j=0;j
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:
通过程序运行的结果可以看出,此程序能够实现在有一个入口一个出口的情况下选择路径的功能,并且就此程序而言,有多条路径可以选择。