首页 > 代码库 > 数据结构之迷宫问题求解(二)迷宫的最短路径
数据结构之迷宫问题求解(二)迷宫的最短路径
上篇文章我们讨论了,迷宫问题的普通求解问题,这篇文章我们继续深入,求迷宫的最短路径.
要想求迷宫的最短路径,一个很简单的方法就是再设置一个Min栈,用来放最短路径,每找到一个出口,就将path栈与Min栈进行比较,如果path栈更小,则赋值给Min.
而在上篇文章中,我们将走过的路径做了标记,每走一个坐标,就把那个坐标置为3,直至找到出口.
因此如果用这种标记方式,显然是会出现问题的.
所以我们需要换种标记方式!
最终....我决定,使出口的值为2,每走一步使当前位置标记变为是上一位置标记再加1.
在这种情况下,我们检测当前位置是否可以通过的函数(CheckIsAccess(int*,sz,Pos))就需要做一些微小的调整....
检测通路函数
/*
*函数功能:检测当前路径是否可以通过(最短路径)
*参数说明:
* Maze:迷宫数组
* sz:迷宫大小
* cur:当前位置坐标
* next:下一位置坐标
* 返回值:可以通过返回true,不能通过返回false
*/
bool CheckIsAccess(int *Maze,size_t sz,Pos cur,Pos next){
//如果下一步路径越界
if((next.x<0||next.x>sz)||
(next.y<0||next.y>sz)){
return false;
}
//下一坐标为0
if(0 == (Maze[next.x*sz+next.y])){
return true;
}
//下一坐标为之前走过的路
if((Maze[next.x*sz+next.y]>Maze[cur.x*sz+cur.y]+1)){
return true;
}
return false;
}
寻找最短路径函数
/*函数功能:求迷宫最短路径
*参数说明:
* Maze:迷宫数组
* sz:迷宫大小
* entry:迷宫入口
* path:走过的路径
* Min:最短路径
* 返回值:可以通过返回true,不能通过返回false
*/
//求最短路径
void GetMazeMinPath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path,stack<Pos> &Min){
path.push(entry);
Pos cur = entry;
Pos next = cur;
//找到出口
if(sz-1 == cur.y){
//第一次赋值给Min 或者path路径比Min短
if(Min.empty()||path.size()<Min.size()){
Min = path;
}
path.pop();
return ;
}
//右
next.x += 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//左
next = cur;
next.x -= 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//上
next = cur;
next.y += 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//下
next = cur;
next.y -= 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
path.pop();
}
完整代码
#ifndef __MAZE_H__
#define __MAZE_H__
#include<iostream>
#include<iomanip>
#include<stack>
#include<assert.h>
namespace Maze{
using namespace std;
//迷宫大小
static const int N = 10;
//迷宫地图文件名
static const char *const FILENAME = "MazeMap.txt";
//坐标
struct Pos{
int x; //横坐标(本质是数组arr[i][j]的j)
int y; //纵坐标(本质是数组arr[i][j]的i)
};
/*
函数说明:从文件中获取迷宫地图
参数说明:
Maze:迷宫地图数组
sz:迷宫大小
返回值:无
*/
void GetMaze(int *Maze,size_t sz){
FILE *fp = fopen(FILENAME,"r");
//打开失败
if(NULL==fp){
//输出错误信息
perror(FILENAME);
//结束程序
exit(1);
}
//将文件中的迷宫地图读入Maze数组内
for(size_t i=0; i<sz; ++i){
for(size_t j=0; j<sz;){
//从文件流中获取字符
char tmp = getc(fp);
//字符为0或为1时,导入数组
if(tmp==‘0‘||tmp==‘1‘){
Maze[i*sz+j]=tmp -‘0‘;
++j;
}else if(EOF==tmp){
//文件已读完,循环还未停止
//说明此处文件中的迷宫地图存在问题
assert(false);
return ;
}
}
}
//关闭文件
fclose(fp);
}
/*
函数说明:打印迷宫
参数说明:
Maze:迷宫地图数组
sz:迷宫大小
返回值:无
*/
void PrintMaze(int *Maze,size_t sz){
cout<<setw(3);
for(size_t i=0; i<sz; ++i){
for(size_t j=0; j<sz; ++j){
cout<<Maze[i*sz+j]<<setw(3);
}
cout<<endl;
}
}
/*
函数说明:检测当前位置是否可以通过
参数说明:
Maze:迷宫地图数组
sz:迷宫大小
cur:当前所在位置
返回值:可以通过返回true,不能通过返回false.
*/
bool CheckIsAccess(int *Maze,size_t sz,Pos cur){
if(cur.x>=0 && cur.x<sz && //行坐标是否越界
cur.y>=0 && cur.y<sz && //列坐标是否越界
Maze[cur.x*sz+cur.y]==0 ){ //所在行列是否可以通过
return true;
}
return false;
}
/*
函数说明:通过栈来进行迷宫求解
参数说明:
Maze:迷宫地图数组
sz:迷宫大小
entry:迷宫入口点
path:用于寻找迷宫出口的栈
返回值:找到出口返回true,没找到返回false.
*/
bool FindMazePath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path){
//将入口压栈
path.push(entry);
//如果栈不为空
while(!path.empty()){
//获取栈顶元素,即上一次走的路径
Pos cur = path.top();
//将其标记为已走过
Maze[cur.x*sz+cur.y] = 3;
//找到出口
if(sz-1==cur.x){
return true;
}
Pos next = cur;
//下一步,向右移动
next.x += 1;
if(CheckIsAccess(Maze,sz,next)){
//可以向右移动,将当前步入栈
path.push(next);
continue;
}
next = cur;
//下一步,向左移动
next.x -= 1;
if(CheckIsAccess(Maze,sz,next)){
//可以向左移动,入栈
path.push(next);
continue;
}
//下一步,向上移动
next = cur;
next.y += 1;
if(CheckIsAccess(Maze,sz,next)){
//可以向上移动
path.push(next);
continue;
}
next = cur;
//向下移动
next.y -= 1;
if(CheckIsAccess(Maze,sz,next)){
//可以向下移动
path.push(next);
continue;
}
//上、下、左、右都不能走
path.pop();
}
return false;
}
/*
*函数说明:根据递归寻找迷宫出口
*参数说明
* Maze:迷宫地图
* sz:迷宫大小
* entry:迷宫入口
* path:用来判断是否存在出口的栈
*返回值:无(如果存在出口,栈为空;如果不存在出口,栈中存在起点坐标)
*/
void FindMazePathR(int *Maze,size_t sz,Pos &entry,stack<Pos> & path){
//将入口压栈
path.push(entry);
Pos cur = entry;
//将已走过的路标记为3
Maze[cur.x*sz+cur.y] = 3;
//找到出口,直接返回
if(sz-1==entry.x){
//将起点坐标弹出
path.pop();
return ;
}
Pos next = cur;
//右
next.x += 1;
if(CheckIsAccess(Maze,sz,next)){
//以当前位置为起点,递归进行下一步
FindMazePathR(Maze,sz,next,path);
}
next = cur;
//左
next.x -= 1;
if(CheckIsAccess(Maze,sz,next)){
FindMazePathR(Maze,sz,next,path);
}
//上
next = cur;
next.y += 1;
if(CheckIsAccess(Maze,sz,next)){
FindMazePathR(Maze,sz,next,path);
}
//下
next = cur;
next.y -= 1;
if(CheckIsAccess(Maze,sz,next)){
FindMazePathR(Maze,sz,next,path);
}
path.pop();
}
/*
*函数功能:检测当前路径是否可以通过(最短路径)
*参数说明:
* Maze:迷宫数组
* sz:迷宫大小
* cur:当前位置坐标
* next:下一位置坐标
* 返回值:可以通过返回true,不能通过返回false
*/
bool CheckIsAccess(int *Maze,size_t sz,Pos cur,Pos next){
//如果下一步路径越界
if((next.x<0||next.x>sz)||
(next.y<0||next.y>sz)){
return false;
}
//下一坐标为0
if(0 == (Maze[next.x*sz+next.y])){
return true;
}
//下一坐标为之前走过的路
if((Maze[next.x*sz+next.y]>Maze[cur.x*sz+cur.y]+1)){
return true;
}
return false;
}
/*
*函数功能:求迷宫最短路径
*参数说明:
* Maze:迷宫数组
* sz:迷宫大小
* entry:迷宫入口
* path:走过的路径
* Min:最短路径
* 返回值:可以通过返回true,不能通过返回false
*/
//求最短路径
void GetMazeMinPath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path,stack<Pos> &Min){
path.push(entry);
Pos cur = entry;
Pos next = cur;
//找到出口
if(sz-1 == cur.y){
//第一次赋值给Min 或者path路径比Min短
if(Min.empty()||path.size()<Min.size()){
Min = path;
}
path.pop();
return ;
}
//右
next.x += 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//左
next = cur;
next.x -= 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//上
next = cur;
next.y += 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
//下
next = cur;
next.y -= 1;
if(CheckIsAccess(Maze,sz,cur,next)){
Maze[next.x*sz+next.y] = Maze[cur.x*sz+cur.y]+1;
GetMazeMinPath(Maze,sz,next,path,Min);
}
path.pop();
}
}
#endif
测试代码
#include"Maze.h"
using namespace Maze;
void MazeTest(){
int arr[N][N]; //迷宫地图
Pos entry = {2,0}; //起点坐标
stack<Pos> path; //栈
stack<Pos> Min; //最短路径
GetMaze((int *)arr,N); //将文件中迷宫导入到arr数组中
arr[2][0] = 2; //将入口标记为2
PrintMaze((int *)arr,N);//打印迷宫
GetMazeMinPath((int *)arr,N,entry,path,Min);//找迷宫出口
cout<<endl<<endl; //换行处理(使界面更整齐)
PrintMaze((int *)arr,N);//打印走过的迷宫
}
int main(){
MazeTest();
return 0;
}
总结：这块东西,还是蛮需要深入研究的,尤其对于那些对递归程序理解的不够好的同学,建议,一步一步的跟入程序,完成整个过程.当然求迷宫最短路径,这显然不是唯一的办法,更多的方法,以后再讨论吧!
附上工程文件:http://pan.baidu.com/s/1eSJr1YE(VS2010)
数据结构之迷宫问题求解(二)迷宫的最短路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。