2022年迷宫递归算法 .pdf

《2022年迷宫递归算法 .pdf》由会员分享，可在线阅读，更多相关《2022年迷宫递归算法 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include #include #define W 80 /迷宫宽的最大值#define H 60 /迷宫高的最大值/* 迷宫单元格状态: VIA: 已经过 ;BLOCK: 阻塞 ;EMPTY: 空的 . */ typedef enum VIA,BLOCK,EMPTY MazeCellStatus; typedef struct int x,y; /单元格的坐标 CellType; /迷宫单元格的类型typedef struct CellType pathW*H; /经过路径int length; /经过长度 MazePathType; /迷宫路线类型/= void outSolution

2、(MazePathType mazePath); /输出迷宫问题的解void trySolution(MazeCellStatus mazeW,int w,int h,CellType exit, CellType cur,MazePathType mazePath);/试探求解下一位置void mazeSolution(MazeCellStatus mazeW,int w,int h, CellType entry,CellType exit); /迷宫问题/= /* 主函数部分 */ int main(void) MazeCellStatus mazeHW = EMPTY ,BLOCK,B

3、LOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK, EMPTY ,BLOCK,EMPTY,EMPTY ,BLOCK,EMPTY ,EMPTY ,EMPTY ,BLOCK,BLOCK, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - EMPTY ,EMPTY ,EMPTY ,BLOCK,BLOCK,EMPTY,BLOCK,EMPTY ,EMPTY ,BLOCK, EMPTY ,BLOCK

4、,BLOCK,EMPTY,EMPTY ,EMPTY ,BLOCK,BLOCK,EMPTY,BLOCK, EMPTY ,EMPTY ,EMPTY ,EMPTY ,EMPTY ,EMPTY ,EMPTY ,EMPTY ,EMPTY ,BLOCK, BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,EMPTY,EMPTY, ; CellType entry = 0,0; /*入口位置 */ CellType exit = 9,5; /*出口位置 */ int h = 6,w = 10; /* 迷宫的高与宽 */ mazeSolution(maze,w,h

5、,entry,exit); /求解迷宫return 0; /= void mazeSolution(MazeCellStatus mazeW,int w,int h, CellType entry,CellType exit) MazePathType mazePath; mazePath.length = 0; /*迷宫路线初始长度为0*/ /* 将入口存入路径，作为路径的起始点*/ mazePath.pathmazePath.length.x = entry.x; mazePath.pathmazePath.length.y = entry.y; mazePath.length +; /路

6、径长自增1 trySolution(maze,w,h,exit,entry,mazePath); / 用递归求解迷宫问题 void trySolution(MazeCellStatus mazeW,int w,int h,CellType exit, CellType cur,MazePathType mazePath) int i; /试探求解下一位置int xShift4 = 0,0,-1,1; /相邻位置相对于当前位置的x 坐标int yShift4 = -1,1,0,0; /相邻位置相对于当前位置的y 坐标CellType adjCell; /当前位置的相邻位置if(cur.x = e

7、xit.x & cur.y = exit.y) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - /已达到出口，输出解outSolution(mazePath); else for(i = 0; i = 0 & adjCell.y = 0 & adjCell.x w & adjCell.y h & (mazeadjCell.yadjCell.x = EMPTY) /相邻位置在迷宫内，并且为空白/将相邻位置存入路径中mazePath

8、.pathmazePath.length.x = adjCell.x; mazePath.pathmazePath.length.y = adjCell.y; mazePath.length +; /路径长自增1 mazeadjCell.yadjCell.x = VIA; /经过相邻位置/对相邻位置进行递归trySolution(maze,w,h,exit,adjCell,mazePath); /*从路径中去掉adjCell，路径长度将自减1*/ mazePath.length -; /*恢复相邻位置为空白，回溯*/ mazeadjCell.yadjCell.x = EMPTY; void o

9、utSolution(MazePathType mazePath) /输出迷宫的解static int num = 0; int i; printf( 第%d 条路径： /n,+ num); /num 为当前以求得解得个数for(i = 0; i mazePath.length; i +) printf(%d,%d),mazePath.pathi.x,mazePath.pathi.y); if(i + 1)%5 = 0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - printf(/n); printf(/n/n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -