企业网站建设 骆,网站建设厂商,邯郸网站建设信息,联邦快递网站建设的目标首先来看一下迷宫简易图 我们用 0 来表示该位置是墙, 用 1 来表示该位置是路. 所以, 我们在处理迷宫问题的时候可以将其看成一个二维数组即可, 而对应的每一条路我们可以用坐标的形式将其表示, 所以还需要…首先来看一下迷宫简易图 我们用 0 来表示该位置是墙, 用 1 来表示该位置是路. 所以, 我们在处理迷宫问题的时候可以将其看成一个二维数组即可, 而对应的每一条路我们可以用坐标的形式将其表示, 所以还需要有一个结构体来描述对应的点的 1. 相关数据结构
typedef struct Maze
{int map[MAX_ROW][MAX_COL];
}Maze;
typedef struct Point
{int row;int col;
}Point;
2.迷宫初始化 所谓的初始化迷宫就是将这个二维数组初始化, 我们自己定义一个二维数组, 然后将其每一个值赋值给我们的迷宫地图即可
void MazeInit(Maze* maze)
{if(maze NULL){return;}int Map[MAX_ROW][MAX_COL] {{0, 1, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 1, 1, 1, 1, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 0}};int row 0;int col 0;for(; row MAX_ROW; row){for(col 0; col MAX_COL; col){maze - map[row][col] Map[row][col];}}
}
3.迷宫探索 迷宫探索即就是从给出的迷宫入口开始, 一直往后探索, 直到找到出口为止. 我们利用函数在递归的过程中会形成栈桢的特性, 依次将我们所探索的为位置进行压栈, 在此过程中, 我们必须得判断当前的点是否合法, 同时必须判断当前的点是否可以落脚, 如果可以落脚, 就现将该位置标记, 然后判断当前位置是否是出口, 如果是出口, 说明迷宫探索完毕, 如果不是出口, 那么我们就得必须找下一个可以落脚的位置, 即我们依次按照顺时针的方向依次遍历当前位置四周的四个点(up, rught, down, left), 只要我们发现有一个点可以落脚, 我们就将当前位置对应的点入栈(调用函数本身), 当四个方向都已经走完了, 那么我们就得往回退, 即就是对应的出栈过程了.具体如下图
void _GetPath(Maze* maze, Point cur, Point entry)
{if(maze NULL){return;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return;}if(entry.row 0 || entry.row MAX_ROW || entry.col 0 || entry.col MAX_COL){return;}printf((%d, %d)\n, cur.row, cur.col);//判断当前点是否可以落脚if(CanStay(maze, cur))//如果可以落脚, 就给当前位置标记//如果当前点是出口, 则说明找到了一条路按顺时针方向探测四个相邻点, 递归调用函数自身, {Mark(maze, cur);if(IsExit(maze, cur, entry)){printf(找到了一条路\n);return;}//递归时更新 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);}else{return;}
}void GetPath(Maze* maze, Point entry)
{if(maze NULL){return;//非法输入}if(entry.row 0 || entry.row MAX_ROW || entry.col 0 || entry.col MAX_COL){return;}//辅助完成递归_GetPath(maze, entry, entry);MazePrint(maze);
}
4.判断是否可以落脚 即先判断迷宫数据结构是否输入合法, 接下来就是判断当前位置是否合法, 如果不合法就退出, 如果当前位置对应的值是 1, 则说明能落脚, 否则就说明不能落脚.
int CanStay(Maze* maze, Point cur)
{if(maze NULL){return 0;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return 0;}if(maze - map[cur.row][cur.col] 1){return 1;}return 0;
}
5.判断出口 如果该位置到达迷宫边界, 并且不等于入口位置, 则说明到达出口
int IsExit(Maze* maze, Point cur, Point entry)
{if(maze NULL){return 0;}if(cur.row entry.row cur.col entry.col){return 0;}if(cur.row MAX_ROW -1 || cur.row 0 || cur.col MAX_COL -1 || cur.col 0){return 1;}return 0;
}
6.标记 将当前位置的值赋值为2
void Mark(Maze* maze, Point cur)
{if(maze NULL){return;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return;}maze - map[cur.row][cur.col] 2;
}
7.打印迷宫函数
void MazePrint(Maze* maze)
{if(maze NULL){return;//非法输入}int row 0;int col 0;for(; row MAX_ROW; row){for(col 0; col MAX_COL; col){printf(%2d , maze - map[row][col]);}printf(\n);}
} 依次将回溯点打印出来,运行结果如图
