1.自然语言描述 对于一般的连续空间（可能是一维、二维、三维乃至更高维）中探索最短路，就是用BFS去解决。 记录路径：若要记录从起点到终点的路径，可以反向BFS，从终点搜索到起点，同时记录路径中每个点的前一个点。这样，达到起点后，再从起点开始顺着记录的点输出，显示从起点到终点的路径。
2.代码描述 题目：Acwing 1076.迷宫问题 题目链接
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int MAXN=1010; int n,s[MAXN][MAXN],cnt; PII path[MAXN][MAXN]; int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; void bfs(int sx,int sy) { queue<PII> q; q.push({sx,sy}); memset(path,-1,sizeof(path));//初始化路径记录数组 path[sx][sy]={0,0}; while(!q.empty()){ auto t=q.front(); q.pop(); int x=t.first,y=t.second; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a<0||a>=n||b<0||b>=n) continue; if(!s[a][b]&&path[a][b].x==-1){//不需要st数组,这里如果新点没有被更新过,也就是它未被遍历过 path[a][b]={x,y};//记录前一个点 q.push({a,b}); } } } } int main(void) { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>s[i][j]; bfs(n-1,n-1); PII end(0,0); while(1){ cout<<end.x<<' '<<end.y<<endl; if(end.x==n-1&&end.y==n-1) break;//直到输出到终点 end=path[end.x][end.y]; } return 0; }