|
int beginX, int beginY, int endX, int endY) {
int kbz = 1;
//待查找的节点
stack<Node> lopenlist;
//节点不在地图范围
if (beginX < 0 || beginY < 0 || beginX >= M || beginY >= M)
return 0;
//起始点加入寻找列表
closelist.push_back({ beginX,beginY });
//找到节点
if ((beginX == endX) && (beginY == endY)) {
//将该节点添加到路径
path.push({ beginX,beginY });
return 1;
}
#pragma region 查找目标节点周围四个节点，如果要增加斜线功能，可以在此添加
//检查(beginX,beginY+1)节点
if (beginY + 1 < M && maze[beginX][beginY + 1].em == 1) {
//该节点没找过 加入待查找节点列表
if (!FindCloseList({ beginX,beginY + 1 })) {
lopenlist.push({ beginX,beginY + 1 });
}
}
//检查(beginX,beginY-1)节点
if (beginY - 1 >= 0 && maze[beginX][beginY - 1].em == 1)
{
if (!FindCloseList({ beginX,beginY - 1 })) {
lopenlist.push({ beginX,beginY - 1 });
}
}
//检查(beginX-1,beginY)节点
if (beginX - 1 >= 0 && maze[beginX - 1][beginY].em == 1) {
if (!FindCloseList({ beginX - 1,beginY })) {
lopenlist.push({ beginX - 1,beginY });
}
}
//检查(beginX+1,beginY)节点
if (beginX + 1 < M &&maze[beginX + 1][beginY].em == 1) {
if (!FindCloseList({ beginX + 1,beginY })) {
lopenlist.push({ beginX + 1,beginY });
}
}
#pragma endregion
//遍历每一个待查找的节点
while (!lopenlist.empty())
{
//取出一个节点
int x = lopenlist.top().X;
int y = lopenlist.top().Y;
lopenlist.pop();
//递归查找
auto k = FindMaze(x, y, endX, endY);
//找到就证明该节点为路径点，加入路径栈中
if (k)
{
path.push({ beginX,beginY });
return kbz + k;
}
}
return 0;
}
int main() {
//初始化
Init();
//制造迷宫
GenMaze();
//输出迷宫
OutMaze();
//寻找路径
if (!FindMaze(1, 0, M - 2, M - 1))
{
cout << "没找到出口";
return -1;
}
//依次从栈中取出每一个路径
while (!path.empty())
{
cout << "(" << path.top().X << "," << path.top().Y << ")";
maze[path.top().X][path.top().Y].em = 3;
path.pop();
if (!path.empty())
cout << ",";
}
cout << endl;
cout << "--------------------------------------------" << endl;
OutMaze();
system("pause");
return 0;
}
|