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

一、程序题目： 问题描述: 设二维数组maze[m][n]为0 表示此路可通,为1表示此路不通.入口是maze[1][1]出口为maze[m][n]且maze[1][1]=0, maze[m][n]=0. 编写寻找从入口到出口的一条最短路径的程序 搜索法: 必须沿8个方向搜索. 二、算法的主要思想： 1. 用矩阵表示的迷宫； 2. 将矩阵表示的迷宫转换成无向图，用邻接表存储； 3. 对无向图从入口结点开始广度优先搜索； 4. 用一个一维数组存储各个结点的前驱结点的编号； 5. 通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2; 6. 依次类推直到找到出口结点。