实验报告——迷宫问题

实习2 栈的应用 本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。实验课时 　　6课时程序1：迷宫问题［问题描述］

2 实习栈的应用 本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用 他们；同时还将巩固对栈这种结构的构造方法的理解。 实验课时 6课时 1 程序：迷宫问题 ［问题描述］ m×n‘0’‘1’ 以一个的长方阵表示迷宫，和分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 ［基本要求］ 首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程 序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如：对下列数据的迷宫，输出的一条通路为：（1，1，1），（1， 2，2），（2，2，2），… ［测试数据］ 迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。 [实现提示] 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索， 若能走通，则继续往前进；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路 , 都探索到为止如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在 从起点到终点的通道，可以二维数组存储迷宫数据。 [] 程序实现 #include<stdio.h> #include<stdlib.h> //1. 迷宫位置坐标类型 typedefstruct { intx;// 行 inty;// 列 }PosType; #defineMAXENGTH25//25 迷宫最大行列数位 typedefintMazeType[MAXENGTH][MAXENGTH];// 迷宫数列