迷宫求解1--简单迷宫是否存在路径

xiaoxiao2021-02-28  20

假如,有如下迷宫地图: 思路: 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是入口点 }
转载请注明原文地址: https://www.6miu.com/read-2799947.html

最新回复(0)