在一个名为“迷宫之城”的游戏中，玩家需要控制角色穿越一个复杂多变的迷宫，以找到出口并逃脱，给定一个迷宫的二维表示，其中：
1、网格中每个单元可以是空地（0表示），墙壁（1表示），起点（S表示，只有一个），终点（E表示，只有一个）。
2、玩家可以从空地移动到相邻的四个方向（上下左右）的空地，但是不能穿墙。
3、迷宫中可能存在单向门，用特殊字符 (如’D’表示向下可通行的单向门，"U"表示向上可通行的单向门，L和R分别表示左右)标记在空地单元格上。这些单向门仅允许玩家按照指示方向移动，反方向则视为墙壁。
请设计一个算法，找出从起点到终点的最短路径，并返回该路径的长度(以步数计)。如果不存在路径，则返回-1.
【输入格式】
输入为一个二维字符数组maze，表示迷宫的布局
【输出格式】
输出一个整数，表示从起点到终点的最短路径长度(含起点)。如果不存在路径，则输出-1。
【提示】
1、迷宫的大小不会超过100x100。
2、迷宫中只包含一个起点和一个终点。
BFS
struct DXMM {pair<int, int> a;int b;
};void minPathss(vector<vector<char>> &maze) {int rows = maze.size();int cols = maze[0].size();int endX=-1, endY=-1;vector<DXMM> dxm;//符合单向门的网格queue<pair<int, int>> poss;//存放当前可访问位置，先访问亦先被访问vector<vector<int>> visited(rows, vector<int>(cols));visited[0][0] = -1;poss.push(pair<int, int>{0, 0});//记录从哪个方向到达当前该网格，默认-1为起点，0为没有走的默认值，1向上，2向下，3向左，4向右int jump[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };//上下左右的跳跃方式bool over = false;while (!poss.empty()){if (over) break;//已经得到路径，直接退出int x = poss.front().first;int y = poss.front().second;poss.pop();if (maze[x][y] == 'E') {endX = x;endY = y;break;}//如果已经到达目标位置，则直接跳出//出队的网格属于单向门int index = 0;auto it = find_if(dxm.begin(), dxm.end(), [&](DXMM s) {return s.a.first == x && s.a.second == y; });if (it != dxm.end()) {dxm.erase(it);//找到了就删除char ch = maze[x][y];//出队的元素限制的移动方向为chif (ch == 'U') index = 1;if (ch == 'D') index = 2;if (ch == 'L') index = 3;if (ch == 'R') index = 4;}//遍历4个方向for (int i = 0; i < 4; i++){int newX = 0, newY = 0;bool flag = false;if (index != 0){newX = x + jump[index-1][0];newY = y + jump[index-1][1];flag = true;}else{newX = x + jump[i][0];newY = y + jump[i][1];}if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && visited[newX][newY] == 0 && (maze[newX][newY] == '0' || maze[newX][newY] == 'U' || maze[newX][newY] == 'D' || maze[newX][newY] == 'L' || maze[newX][newY] == 'R'|| maze[newX][newY] == 'E')){if (maze[newX][newY] == 'E'){endX = newX;endY = newY;visited[newX][newY] = i + 1;over = true;break;}//既然能进来，那么看看当前单元格上面是否是0，U，D,L,R//if (maze[newX][newY] == 'U' || maze[newX][newY] == 'D' || maze[newX][newY] == 'L'|| maze[newX][newY] == 'R'){if (maze[newX][newY] != '0') {dxm.push_back({ pair<int, int>{newX, newY}, i + 1});}poss.push(pair<int, int>{newX, newY});visited[newX][newY] = i + 1;}if (flag) break;}}//根据历史路径矩阵画出原始路径int stX = endX, stY = endY;if (stX == -1 || stY ==-1 || visited[stX][stY] == 0) {cout << "不存在从左上角到右下角的路线" << endl;return;}//由于从终点到起点是逆序的，因此需要使用栈进行存储stack<pair<int, int>> path;path.push(pair<int, int>{stX, stY});//存在这条路径的话，一定可以从右下角走到左上角while (stX != 0 || stY != 0) {int aX = stX - jump[visited[stX][stY] - 1][0];int aY = stY - jump[visited[stX][stY] - 1][1];path.push(pair<int, int>{aX, aY});stX = aX; stY = aY;//更新当前位置}int pathLens = path.size();cout << "最短路径长度为：" << pathLens << endl;while (!path.empty()) {cout << "[" << path.top().first << "," << path.top().second << "]" << endl;path.pop();}
}
//main
//测试案例：vector<vector<char>> maze = { {'S', '0', '0', '0'},{'0', '1', 'D', '0'},{'0', '0', '0', 'E'},{'0', 'U', '0', '0'} };minPathss(maze);
结果输出:
