用c++求两点间的所有路径代码
时间: 2023-03-13 12:16:36 浏览: 92
可以使用下面的代码来求解两点间的所有路径: #include <iostream>
#include <vector> using namespace std; // 定义矩阵的行和列
#define ROW 10
#define COL 10 // 记录路径的结果
vector<pair<int,int> > path; // 定义矩阵
int maze[ROW][COL] =
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 1, 1, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 1, 1, 0, 1, 1, 1, 1, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 1, 1, 1, 1, 0, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
}; // 判断路径是否有效
bool isValidPath(int x, int y)
{
if(x < 0 || x >= ROW || y < 0 || y >= COL || maze[x][y] != 0)
return false;
return true;
} // 打印路径
void printPath()
{
for(int i=0; i < path.size(); i++)
{
cout << "(" << path[i].first << ", " << path[i].second << ") ";
}
cout << endl;
} // 找到从起点到终点的所有路径
void findAllPaths(int x, int y)
{
// 判断是否到达终点
if(x == ROW-1 && y == COL-1)
{
path.push_back(make_pair(x, y));
printPath();
path.pop_back();
return;
}
// 判断路径是否有效
if(isValidPath(x, y))
{
// 把当前点加入到路径中
path.push_back(make_pair(x, y));
// 尝试按照不同的方向前进
findAllPaths(x+1, y);
findAllPaths(x, y+1);
findAllPaths(x-1, y);
findAllPaths(x, y-1);
// 回溯
path.pop_back();
}
} // 主函数
int main()
{
// 先把起点加入到路径中
path.push_back(make_pair(0, 0));
// 从起点开始尝试找到所有的路径
findAllPaths(0, 0);
return 0;
}