迷宫问题

#include <iostream>
#include <stack>
#include <vector>
#include <climits>
using namespace std;// 迷宫大小
const int ROW = 5;
const int COL = 5;// 迷宫（0：可走，1：墙，起点(0,0)，终点(4,4)）
int maze[ROW][COL] = {{0, 1, 0, 0, 0},{0, 1, 0, 1, 0},{0, 0, 0, 1, 0},{0, 1, 1, 0, 0},{0, 0, 0, 1, 0}
};// 方向数组：上、下、左、右
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};// 记录所有路径
vector<vector<pair<int, int> > > allPaths;  // 旧标准中>>需分开写为> >
// 记录最短路径及长度
vector<pair<int, int> > shortestPath;  // 旧标准中>>需分开写为> >
int minLength = INT_MAX;// 栈元素的结构体（替代tuple）
struct StackElem {int x;int y;int dirIdx;vector<pair<int, int> > path;  // 旧标准中>>需分开写为> >
};// 深度优先搜索（栈实现）
void dfsMaze() {stack<StackElem> st;  // 存储自定义结构体的栈// 起点入栈初始化StackElem startElem;startElem.x = 0;startElem.y = 0;startElem.dirIdx = 0;startElem.path.push_back(make_pair(0, 0));st.push(startElem);// 标记起点已访问maze[0][0] = 2;while (!st.empty()) {StackElem topElem = st.top();st.pop();int x = topElem.x;int y = topElem.y;int dirIdx = topElem.dirIdx;vector<pair<int, int> > path = topElem.path;  // 旧标准中>>需分开写为> >// 到达终点(4,4)，记录路径if (x == ROW - 1 && y == COL - 1) {allPaths.push_back(path);// 更新最短路径if (path.size() < minLength) {minLength = path.size();shortestPath = path;}continue;}// 探索4个方向for (int i = dirIdx; i < 4; ++i) {int nx = x + dir[i][0];int ny = y + dir[i][1];// 判断新坐标是否合法：在迷宫范围内、可走（0）、未访问if (nx >= 0 && nx < ROW && ny >= 0 && ny < COL && maze[nx][ny] == 0) {// 标记新节点为已访问maze[nx][ny] = 2;// 复制当前路径，添加新节点vector<pair<int, int> > newPath = path;  // 旧标准中>>需分开写为> >newPath.push_back(make_pair(nx, ny));// 当前节点重新入栈（继续探索下一个方向）StackElem currElem;currElem.x = x;currElem.y = y;currElem.dirIdx = i + 1;currElem.path = path;st.push(currElem);// 新节点入栈（探索该方向）StackElem nextElem;nextElem.x = nx;nextElem.y = ny;nextElem.dirIdx = 0;nextElem.path = newPath;st.push(nextElem);break;  // 进入下一层搜索}}// 所有方向探索完毕，回溯（取消当前节点的访问标记）if (dirIdx == 4) {maze[x][y] = 0;}}
}// 输出所有路径
void printAllPaths() {cout << "迷宫的所有路径：" << endl;for (int i = 0; i < allPaths.size(); ++i) {cout << "路径" << i + 1 << "：";for (vector<pair<int, int> >::iterator it = allPaths[i].begin(); it != allPaths[i].end(); ++it) {  // 旧标准迭代器写法cout << "(" << it->first << "," << it->second << ") ";}cout << "（长度：" << allPaths[i].size() << "）" << endl;}
}// 输出最短路径
void printShortestPath() {cout << "\n第一条最短路径：";for (vector<pair<int, int> >::iterator it = shortestPath.begin(); it != shortestPath.end(); ++it) {  // 旧标准迭代器写法cout << "(" << it->first << "," << it->second << ") ";}cout << "（长度：" << minLength << "）" << endl;
}int main() {dfsMaze();printAllPaths();printShortestPath();return 0;
}