假如，有如下迷宫地图： 思路： 1.判定当前点是否能落脚 2.如果能落脚进行标记 3.判断当前点是否是出口 a)如果是出口，则找到了一条路径 b)如果不是出口，则以当前点为准则，采用递归的方式顺时针方向继续探测四周 解析： 这里判定落脚规则是，如果当前点为0即是墙，不能落脚，当前点是已经标记过的点，不能落脚； 这里的标记是，将已经走过的点赋值为2；
代码如下：
#include <stdio.h> #include <stdlib.h> #include "seqstack.h" #define MAX_ROW 6 #define MAX_COL 6 typedef struct Maze { int map[MAX_ROW][MAX_COL]; }Maze; void MazeInit(Maze* maze) { int map[MAX_ROW][MAX_COL] = { {0,1,0,0,0,0}, {0,1,1,1,0,0}, {0,1,0,1,0,0}, {0,1,0,1,1,0}, {0,1,1,0,0,0}, {0,0,1,0,0,0}, }; int i = 0; for(i=0;i<MAX_ROW;i++){ int j = 0; for(j=0;j<MAX_COL;j++){ maze->map[i][j] = map[i][j]; } } return; } int CanStay(Maze* maze,Point pt){ //1.如果这个点在地图外肯定不能落脚 if(pt.row < 0 || pt.row >= MAX_ROW || pt.col < 0 || pt.co return 0; } //2.如果pt在地图内的话，如果这个位置值是1，就能落脚，如果 int value = maze->map[pt.row][pt.col]; if(value == 1){ return 1; } return 0; } //标记 void Mark(Maze* maze , Point cur){ maze->map[cur.row][cur.col] = 2; } //如果是出口，返回1，否则返回0 int IsEixt(Maze* maze ,Point cur,Point entry) { (void) maze;//消除警告 //1.当前点是不是入口，如果是入口，那肯定不是出口 if(cur.row == entry.row && cur.col == entry.col){ return 0; } //2.如果点在地图的边界上说明是出口 if(cur.row == 0 || cur.row == MAX_ROW - 1 || cur.col == 0 return 1; } return 0; } //每次走到下一个点都会递归的调用下面这个函数 void _GetPath(Maze* maze,Point cur,Point entry){ printf("cur:(%d,%d)\n",cur.row,cur.col); //1.判定当前点是否能落脚 if(!CanStay(maze,cur)){ return; } //2.如果能落脚就给当前位置做标记 Mark(maze,cur); //3.如果当前点是出口，说明找到了一条出路，探测就结束 if(IsEixt(maze,cur,entry)){ printf("找到了一条路径\n"); return; } //4.如果当前点不是出口，就按照顺时针探测四个相邻点， // 递归的调用函数自身，递归时，更新cur点 //（每次递归的时候，点都是下一次要走的点，这个点能不能走交给递归函数实现） Point up = cur; up.row -= 1; _GetPath(maze,up,entry); Point right = cur; right.col += 1; _GetPath(maze,right,entry); Point down = cur; down.row += 1; _GetPath(maze,down,entry); Point left = cur; left.col -= 1; _GetPath(maze,left,entry); } void GetPath(Maze* maze,Point entry){ if(maze == NULL){ return; } //使用下面的函数辅助我们完成递归 _GetPath(maze,entry,entry);//第一个entry是当前走到的点，第二个entry是入口点 }