首页 > 代码库 > 回溯法找迷宫最短路径
回溯法找迷宫最短路径
有一个二维数组，0表示路，-1表示墙，求其中任意两点的最短路径
我们先看，怎么求一条路径：求两点路径是一个数据结构上的典型的迷宫问题，解决办法如下：
从一点开始出发，向四个方向查找（上，右，下，左），每走一步，把走过的点的值+1，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进，如果前方已经无路可走，则返回，路径退栈，这样递归调用，直到找到终点为止。
如果我们调整查找的顺序，改为左、右、上、下，可能会得到更短的路径，但这种方法不能保证一定是最短路径。
经过网上查找、看书，以下方法可以得到最短路径：
按照左、右、上、下方向，每走一步，就把将要走的节点赋值为此节点值+1，走过的路径也可以重复行走。条件是本节点值+1必须小于已走过的节点的值(墙不能走)，这样遍历所有的节点，便可以记录最短的路径。
C++代码实现如下：
#include <iostream>
#include <iomanip>
#include <stack>
using namespace std;
class Maze
{
public:
//成员变量初始化
Maze(size_t start_x, size_t start_y, size_t end_x, size_t end_y)
:m_start(Node(start_x, start_y)), m_end(Node(end_x, end_y))
{
m_maze[start_x][start_y] = 1; //迷宫入口初始化为1，避免重复走
}
//查找最短路径
void searchPath()
{
searchPath(m_tempPath, m_start, m_end);//调用私有函数
}
//打印最短路径走过的点
void printPath()
{
while(!m_path.empty())
{
cout << '(' << m_path.top().m_x << ','
<< m_path.top().m_y << ')'<< "——>"
<<m_maze[m_path.top().m_x][m_path.top().m_y]
<< endl;
m_path.pop();
}
}
//打印遍历后的数组节点值
void printMaze()const
{
for(size_t i = 0; i < 10; ++i)
{
for(size_t j = 0; j < 10; ++j)
{
cout << setw(2) << m_maze[i][j] << ',';
}
cout << '\b' << endl;
}
}
private:
//定义节点
class Node
{
public:
int m_x;
int m_y;
Node(int x = 0, int y = 0) : m_x(x), m_y(y){}
const Node operator+ (const Node& that)const
{
Node node;
node.m_x = m_x + that.m_x;
node.m_y = m_y + that.m_y;
return node;
}
};
//查找
void searchPath(stack<Node>& path,
const Node& start, const Node& end)
{
if(start.m_x == end.m_x && start.m_y == end.m_y) //走到终点
{
if(path.size() < m_path.size() //当前路径更短 或 为第一个找到的路径
|| m_path.empty())
m_path = path;
return;
}
for( size_t i = 0; i < 4; ++i) //遍历四个方向
{
Node nextNode = start + offset[i]; //加上偏移量
if(isCanGo(start, nextNode)) //如果可以通过
{
m_maze[nextNode.m_x][nextNode.m_y] = m_maze[start.m_x][start.m_y] + 1;
path.push(nextNode); //节点入栈
searchPath(path, nextNode, end); //递归查找
path.pop(); //弹出栈顶
}
}
}
//判断start到next能否走通
bool isCanGo(const Node& start, const Node& next)const
{
int x = next.m_x, y = next.m_y;
int preValue = http://www.mamicode.com/m_maze[start.m_x][start.m_y]; //节点值>结果如下：（坐标后数字为当前走过节点数）
![]()
回溯法找迷宫最短路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。