迷宫最短路径求解--c++

【代码】

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define ROW 8
#define COL 8
//测试迷宫数据
int maze[ROW][COL] = {{0,0,0,1,0,0,0,0},{0,1,0,1,0,1,0,1},{0,1,0,0,0,1,0,1},{0,1,0,1,1,1,0,1},{0,1,0,1,1,0,0,0},{0,1,1,0,0,0,1,1},{0,0,0,0,1,0,1,1},{1,1,1,0,0,0,0,0}
};typedef struct
{int index;  //当前点在路径结点数组中的位置int parent_idx; //当前经过点的上一个点在路径结点数组中的位置int x, y;   //当前点的坐标
}PathNode;
//迷宫中每个点第一次出现时放入数组，为后续查找路径提供信息
PathNode path[ROW * COL];
//已访问数组，表示每个点是否已被访问
bool vis[ROW][COL] = { false };
//方向结构体
typedef struct
{int xstep, ystep;
}Dir;
Dir dir[4] = { {-1,0},{0,-1},{1,0},{0,1} };
bool validate(int x, int y)
{return x >= 0 && x < ROW && y >= 0 && y < COL;
}
//根据出口结点反向查找路径
void identifyPath(PathNode node)
{stack<PathNode>s;int skips = 0;//从最后一个节点逐次入栈，反向找到最短路径上的每个点while (true){s.push(node);if (node.parent_idx == -1)break;node = path[node.parent_idx];}cout << "path:" << endl;while (!s.empty()){node = s.top();s.pop();cout << "(" << node.x << "," << node.y << ")";if (!s.empty()){skips++;cout << "->";}}cout << endl;cout << "path length:" << skips << endl;
}//寻找以（sx，xy）为起点，（ex，ey）为出口的迷宫路径
//使用图的广度优先遍历，从起点开始逐层往外扩散，直到出现出口坐标
void findShortestPath(int sx, int sy, int ex, int ey)
{PathNode pn;int idx = 0;int cnt = 0;//初始化，生成开始结点信息，并放入路径数组中pn.parent_idx = -1;pn.x = sx;pn.y = sy;pn.index = 0;vis[pn.x][pn.y] = true;path[cnt++] = pn;while (1){//找出队列中未访问的第一个元素PathNode node = path[idx++];//搜索四个方向，形成下一步可以通过的坐标for (int j = 0; j < 4; j++){int newx = node.x + dir[j].xstep;int newy = node.y + dir[j].ystep;//如果下一步坐标合法，未被访问且可以通过if (validate(newx, newy) && !vis[newx][newy] && maze[newx][newy] == 0){//生成新的结点PathNode pn;pn.x = newx;pn.y = newy;pn.parent_idx = node.index;pn.index = cnt;//如果为新的结点为出口，确定路径并返回if (newx == ex && newy == ey){identifyPath(pn);return;}//将新的结点放入路径数组中path[cnt++] = pn;//设置该结点已被访问过vis[newx][newy] = true;}}//如果遍历完所有的结点都没有找到出口，说明没有路径if (idx == cnt){cout << "no solution" << endl;break;}}
}int main()
{findShortestPath(0, 0, ROW - 1, COL - 1);return 0;
}