网站建设规模与类别,泛华建设集团有限公司网站,企业内部网站建设,计算机专业哪个学校最好前面介绍了简单的迷宫求解问题, 今天我们就对带环迷宫求出它的最短路径
1.首先来看一个带环迷宫的简单地图 在这张迷宫地图中,我们规定入口点的位置entry的坐标是 (0, 1), 同时, 我们给入口点传一个非法坐标,作为入口点的前一个位置(-1, -1). 接下来的思路就和上一篇的思路是一…前面介绍了简单的迷宫求解问题, 今天我们就对带环迷宫求出它的最短路径
1.首先来看一个带环迷宫的简单地图 在这张迷宫地图中,我们规定入口点的位置entry的坐标是 (0, 1), 同时, 我们给入口点传一个非法坐标,作为入口点的前一个位置(-1, -1). 接下来的思路就和上一篇的思路是一样的的了. 即每次判断当前点是否可以落脚, 如果不能落脚就直接退出, 如果可以落脚, 就将当前位置的点进行入栈操作, 将其标记(和前面不一样了), 接着判断当前点是否是出口, 如果是出口, 就将拿着 cur_path 和 short_path 进行比较, 将较短的保存在 short_path 中, 然后将 cur_path 出栈, 接着再进行回溯. 如果当前点不是出口, 就按照顺序依次探测当前点周围的四个点, 如果四个点都已经探测完了, 就需要回溯, 回溯的同时不要忘记将当前栈 cur_path 出栈
2. 判断当前位置是否可以落脚 判断当前位置是否可以落脚可以分为以下两种情况 (1)当前位置还没有走过 此时地图对应的二维数组的值是 1, 即这个位置一定可以落脚 (2)当前位置如果已经走过, 我们需要借助当前位置的前一个落脚元素来判断当前位置是否可以落脚, 当前一个位置在地图上对应的值加1 小于当前位置在地图上的值的时候, 此时证明该位置就可以落脚, 即 cur pre 1此时就可以落脚
int CanStayWithCircle(Maze* maze, Point cur, Point prev)
{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] 0){return 0;}//在取 prev 之前判断 prev 是否合法if(prev.row -1 prev.col -1){return 1;}//此时的prev 已经不再是入口点的前一个坐标if(prev.row 0 || prev.row MAX_ROW || prev.col 0 || prev.col MAX_COL){return 0;}//当前位置已经走过, 比较 cur 和 prev 的大小关系if(maze - map[cur.row][cur.col] maze - map[prev.row][prev.col] 1){return 1;}//如果当前点是 1 就直接可以落脚if(maze - map[cur.row][cur.col] 1){return 1;}return 0;
}
3. 对当前位置进行标记 对当前位置标记分为两种情况, 第一种就是看当前位置是否为入口, 如果是入口, 就将地图对应的当前位置处的坐标变为2,否则就是让 map[cur.row][cur.col] map[prev.row][prev.col] 1
void MarkShortPathWithCircle(Maze* maze, Point cur, Point prev)
{if(maze NULL){return;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return;}if(prev.row -1 || prev.row MAX_ROW || prev.col -1 || prev.col MAX_COL){return;}if(prev.row -1 prev.col -1){maze - map[cur.row][cur.col] 2;return;}maze - map[cur.row][cur.col] maze - map[prev.row][prev.col] 1;return;
}
3. 迷宫求解递归代码
int CanStayWithCircle(Maze* maze, Point cur, Point prev)
{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] 0){return 0;}//在取 prev 之前判断 prev 是否合法if(prev.row -1 prev.col -1){return 1;}//此时的prev 已经不再是入口点的前一个坐标if(prev.row 0 || prev.row MAX_ROW || prev.col 0 || prev.col MAX_COL){return 0;}//当前位置已经走过, 比较 cur 和 prev 的大小关系if(maze - map[cur.row][cur.col] maze - map[prev.row][prev.col] 1){return 1;}//如果当前点是 1 就直接可以落脚if(maze - map[cur.row][cur.col] 1){return 1;}return 0;
}void MarkShortPathWithCircle(Maze* maze, Point cur, Point prev)
{if(maze NULL){return;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return;}if(prev.row -1 || prev.row MAX_ROW || prev.col -1 || prev.col MAX_COL){return;}if(prev.row -1 prev.col -1){maze - map[cur.row][cur.col] 2;return;}maze - map[cur.row][cur.col] maze - map[prev.row][prev.col] 1;return;
}void _GetShortPathWithCircle(Maze* maze, Point entry, Point cur, SeqStack* cur_path, SeqStack* short_path, Point prev)
{if(maze NULL){return;}if(entry.row 0 || entry.row MAX_ROW || entry.col 0 || entry.col MAX_COL){return;}if(cur.row 0 || cur.row MAX_ROW || cur.col 0 || cur.col MAX_COL){return;}if(cur_path NULL || short_path NULL){return;}//1. 判定当前点是否可以落脚if(CanStayWithCircle(maze, cur, prev) 0){return;}//2. 如果能落脚, 就标记当前点, 并将其入栈到 cur_path中MarkShortPathWithCircle(maze, cur, prev);SeqStackPush(cur_path, cur);//3. 判定当前是否是出口if(IsExit(maze, cur, entry))// a) 如果是出口, 就将 cur_path 和 short_path 比较, 把较短的路径保存到 cur_path 中// 还有一种就是如果 short_path 的长度为 0, 就用 cur_path 代替 short_path ,然后将 cur_path// 出栈, 并且回溯{printf(找到了一条路\n);if(cur_path - size short_path - size || short_path - size 0){SeqStackAssgin(short_path, cur_path);}SeqStackPop(cur_path);return;}// b) 如果不是出口, 以当前点为基准, 顺时针探测 周围四个点Point up cur;up.row - 1;_GetShortPathWithCircle(maze, entry, up, cur_path, short_path, cur);Point right cur;right.col 1;_GetShortPathWithCircle(maze, entry, right, cur_path, short_path, cur);Point down cur;down.row 1;_GetShortPathWithCircle(maze, entry, down, cur_path, short_path, cur);Point left cur;left.col - 1;_GetShortPathWithCircle(maze, entry, left, cur_path, short_path, cur);//4. 如果四个方向都探测过了, 回溯SeqStackPop(cur_path);return;
}void GetShortPathWithCircle(Maze* maze, Point entry, Point prev)
{if(maze NULL){return;//非法输入}if(entry.row 0 || entry.row MAX_ROW || entry.col 0 || entry.col MAX_COL){return;//非法输入}//规定第一个prev点的坐标是(-1, -1)if(prev.row ! -1 prev.col ! -1){return;}//定义两个栈SeqStack cur_path;SeqStack short_path;//分别对这两个栈进行初始化SeqStackInit(cur_path);SeqStackInit(short_path);//辅助递归_GetShortPathWithCircle(maze, entry, entry, cur_path, short_path, prev);SeqStackDebugPrint(short_path, 最短路径);
}
