题目：小 C 最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个 n×m 的迷宫中，看看机器人能不能在最短的时间内到达目的地，可是小 C 不知道最短的时间是多少，现在请你帮他算算机器人到达目的地的最短时间是多少？输出一个整数表示机器人到达目的地的最短时间，如果机器人不能到达目的地，输出 −1。如果能到达，输出方案，满足用时最少，且字典序最小。
代码
#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
struct node{
int x,y,step;
}s;
int n,m;
int vis[MAX][MAX];
char mp[MAX][MAX];
int dis[4][2]={1,0,-1,0,0,1,0,-1};
int bfs()
{
queue<node>q;
node next,p,e;
p.x=s.x;
p.y=s.y;
p.step=0;
vis[p.x][p.y]=1;
q.push(p);
while(!q.empty())
{
e=q.front();
q.pop();
if(mp[e.x][e.y]=='T') return e.step;
for(int i=0;i<4;i++){
next.x=e.x+dis[i][0];
next.y=e.y+dis[i][1];
if(mp[next.x][next.y]=='T') return e.step+1;
if(mp[next.x][next.y]=='.'&&vis[next.x][next.y]==0&&next.x>0&&next.x<=n&&next.y>0&&next.y<=m)
{
vis[next.x][next.y]=1;
next.step=e.step+1;
q.push(next);
}
}
}
return 0;
}
int main()
{
while(cin>>n>>m)
{
memset(vis,0,sizeof(vis));
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++)
{
cin>>mp[i]+1;
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='S')
{
s.x=i;
s.y=j;
}
}
}
int ans=bfs();
if(ans==0) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
}
请问一下如何输出最短路径啊？谢谢
迷宫里面到底是什么样式的迷宫，终点位置在哪，墙体用什么符号表示，路径用什么符号表示，说不清楚很容易搞错，仅拿代码来看 'T'是终点，‘.’是可走的路径，字典序最小的意思应该是向上，向左优先，其实改一下广搜，在最后特判一下字典序也行。不过还是建议算法竞赛的问题在洛谷上提问比较好，这里大概解决不了这种问题
【以下回答由 GPT 生成】
问题可以使用广度优先搜索（BFS）算法来解决。下面是修改后的代码来输出最短路径：
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <climits>
using namespace std;
struct Point {
int x;
int y;
string path;
};
vector<Point> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool isValidMove(int x, int y, int n, int m, vector<vector<char>>& maze, vector<vector<bool>>& visited) {
if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == '#' || visited[x][y]) {
return false;
}
return true;
}
string shortestPath(vector<vector<char>>& maze, int n, int m, Point start, Point end) {
queue<Point> q;
q.push(start);
vector<vector<bool>> visited(n, vector<bool>(m, false));
visited[start.x][start.y] = true;
while (!q.empty()) {
Point curr = q.front();
q.pop();
int x = curr.x;
int y = curr.y;
string path = curr.path;
if (x == end.x && y == end.y) {
return path;
}
for (Point dir : directions) {
int newX = x + dir.x;
int newY = y + dir.y;
if (isValidMove(newX, newY, n, m, maze, visited)) {
visited[newX][newY] = true;
q.push({newX, newY, path + dir});
}
}
}
return "-1";
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<char>> maze(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
}
}
Point start, end;
cin >> start.x >> start.y >> end.x >> end.y;
start.path = "";
string shortest = shortestPath(maze, n, m, start, end);
cout << shortest << endl;
return 0;
}
以上代码通过一个队列来存储路径上的每一步，接着使用广度优先搜索算法来遍历每一步的可能移动方式。最后，找到目标位置时即可返回最短路径。如果机器人无法到达目标位置，则输出 -1。这个算法使用了一个二维数组 visited 来记录已经访问过的位置，以防止重复访问。该算法的时间复杂度是 O(n * m)，其中 n 和 m 分别是迷宫的行数和列数。
【相关推荐】