这个问题难受了半天终于搞懂了，来给分享一下
 先弄个例子看看；
 
B.wzy的大冒险——出发咯QAQ
 
wzy踏上了冒险的旅程。
 现在他从地精手里买了一份地图，地图上有n个城镇。
 他从第一个城镇出发，走向（没钱只能走）第n个城镇，现在，请你帮wzy找到一条最短的路径，并倒序（从n到1）输出一条最短路径。
 地精小提示：路是单向的QAQ。
 
输入格式
 
第一行两个数n,m ，(1≤n≤103,1≤m≤103)
 
接下来m行，每行三个数x,y,z，表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤103).
 
输出格式
 
第一行一个整数表示 1 到 n 的最短距离；
 第二行倒序输出这条路径。
 
样例
 
input
 5 7
 1 2 69
 1 3 87
 1 4 79
 2 5 94
 2 3 10
 3 5 79
 4 5 43
 output
 122
 5 4 1
 
解题思路
 
一看这道题就是求最短路径，就是输出路径这一点要搞清楚,看代码解析。
 
#pragma GCC optimize(2)
#include<bits/stdc++.h>
const int inf =0x3f3f3f3f;
using namespace std;
const int maxn =1e3+10;
typedef long long ll;
int way[maxn][maxn];//记录从点a到点b的距离 
int dis[maxn];//某线段的权值 
int flag[maxn];//用来标记走过的点 
int d[maxn];//用来存路径，具体存法是他上一个点是从那来的，不懂往下看 
int n,m;//n是顶点个数，m有多少个边 
int dijkstra()
{
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;i++)
	{
		dis[i]=way[1][i];//从1到第i的顶的距离赋给dis 
		if(way[1][i]!=inf)
		{
			d[i]=1;//记录i点事由1到达的 
		}
	}
    flag[1]=1; dis[1]=0;
    int x;
	for(int i=1;i<=n;i++)//循环n次每次找到一个最近的点 ，走过的点标记 
	{
		int ans=inf;
		for(int j=1;j<=n;j++)
		{
			if(ans>dis[j]&&!flag[j])
			{
				ans=dis[j];
				x=j;
			}
		}
		flag[x]=1;//已经找到给一个标记 
		for(int i=1;i<=n;i++)
		{
			if(!flag[i])
			{
				if(dis[i]>dis[x]+way[x][i])
				{
					dis[i]=dis[x]+way[x][i];
					d[i]=x;//记录到i点事由x过来的 
				}			
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			way[i][j]=inf;//把每条路先赋成最大 
		}
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		way[a][b]=c;//记录a到b的距离 
	}
	dijkstra();
	cout<<dis[n]<<endl;//输出最短距离 
	int t=n;
	cout<<n<<" ";//输出路径的最后一个点 
	int s=1;
	while(t!=1)
	{
		t=d[t];
		if(s)
		{
			cout<<t;//注意下输出 
			s=0;
		}
		else cout<<" "<<t;	
	}
	return 0;
} 
 
欢迎使用Markdown编辑器
 
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。
 
新的改变
 
我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：
 
全新的界面设计 ，将会带来全新的写作体验；
在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；
增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；
全新的 KaTeX数学公式 语法；
增加了支持甘特图的mermaid语法 功能；
增加了 多屏幕编辑 Markdown文章功能；
增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；
增加了 检查列表 功能。
 
功能快捷键
 
撤销：Ctrl/Command + Z
 重做：Ctrl/Command + Y
 加粗：Ctrl/Command + B
 斜体：Ctrl/Command + I
 标题：Ctrl/Command + Shift + H
 无序列表：Ctrl/Command + Shift + U
 有序列表：Ctrl/Command + Shift + O
 检查列表：Ctrl/Command + Shift + C
 插入代码：Ctrl/Command + Shift + K
 插入链接：Ctrl/Command + Shift + L
 插入图片：Ctrl/Command + Shift + G
 
合理的创建标题，有助于目录的生成
 
直接输入1次#，并按下space后，将生成1级标题。
 输入2次#，并按下space后，将生成2级标题。
 以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。
 
如何改变文本的样式
 
强调文本 强调文本
 
加粗文本 加粗文本
 
标记文本
 
删除文本
 
 
 
引用文本
 
 
H2O is是液体。
 
210 运算结果是 1024.
 
插入链接与图片
 
链接: link.
 
图片: 
 
带尺寸的图片: 
 
居中的图片: 
 
居中并且带尺寸的图片: 
 
当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。
 
如何插入一段漂亮的代码片
 
去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.
 
// An highlighted block
var foo = 'bar';
 
生成一个适合你的列表
 
项目 
  
项目 
    
项目
 
 
 
项目1
项目2
项目3
 
 计划任务
 完成任务
 
创建一个表格
 
一个简单的表格是这么创建的：
 
项目
Value
电脑
$1600
手机
$12
导管
$1
设定内容居中、居左、居右
 
使用:---------:居中
 使用:----------居左
 使用----------:居右
 
第一列
第二列
第三列
第一列文本居中
第二列文本居右
第三列文本居左
SmartyPants
 
SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：
 
TYPE
ASCII
HTML
Single backticks
'Isn't this fun?'
‘Isn’t this fun?’
Quotes
"Isn't this fun?"
“Isn’t this fun?”
Dashes
-- is en-dash, --- is em-dash
– is en-dash, — is em-dash
创建一个自定义列表
 
 
 
  Markdown
  
 

  Text-to-
  HTML conversion tool
 
 
 
  Authors
  
 

  John
 
 
 

  Luke
 
 
 
如何创建一个注脚
 
一个具有注脚的文本。
 
注释也是必不可少的
 
Markdown将文本转换为 HTML。
 
KaTeX数学公式
 
您可以使用渲染LaTeX数学表达式 KaTeX:
 
Gamma公式展示 $\Gamma (n)=(n-1)!\forall n\in \mathbb{N}$ 是通过欧拉积分
 
$$\Gamma (z)={\int }_0^{\infty }{t}^{z-1}{e}^{-t}dt.$$
 
 
 
你可以找到更多关于的信息 LaTeX 数学表达式here.
 
 
新的甘特图功能，丰富你的文章
 

 
 
关于 甘特图 语法，参考 这儿,
 
UML 图表
 
可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：:
 

 
 
这将产生一个流程图。:
 

 
 
关于 Mermaid 语法，参考 这儿,
 
FLowchart流程图
 
我们依旧会支持flowchart的流程图：
 

 
 
关于 Flowchart流程图 语法，参考 这儿.
 
导出与导入
 
导出
 
如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。
 
导入
 
如果你想加载一篇你写过的.md文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，
 继续你的创作。
 
 
 
 
mermaid语法说明 ↩︎
 
注脚的解释 ↩︎
 
 

弗洛伊德算法求最短路径 输出路径
 
弗洛伊德算法其实比较好理解
 这里我用邻接矩阵的储存方法来写
 
一.算法思想
 
1.1
 如果我们要用邻接矩阵来写代码的话，就要储存他的权值信息
 这里我们用map[][]这个二维数组来储存
 其次要输出他的最短路径
 就用path[][]来储存
 
    int map[100][100];
	int path[100][100];
 
1.2
 初始化这个储存权值邻接矩阵
 由于是无环图，自己到自己是 0
 剩下的边的权值我们赋值为MAX
 
for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=max;
 
1.3
 读入边的信息
 如果两个结点i，j之间有权值，就把他赋值给map[i][j]
 并且这个时候将j赋值给path[i][j]
 
	cout<<"输入点1到点2的距离"<<endl; 
    for(int i=1; i<=m; i++)
    {
        cin>>t1>>t2>>t3;
        map[t1][t2]=t3;
        map[t2][t1]=t3;
        path[t1][t2]=t2;
    }
 
这个路径的赋值如果在后面有更优解
 将会更新这个值，如果没有，那说明i直接到j就是最短的
 
1.4 核心算法
 这个核心算法使用一个三重循环来一个一个找最优解
 第一重循环控制中转结点k
 第二重控制起始结点i
 第三重控制终止结点j
 
如果我们发现i->k->j的路径小于i->j的
 那我们就更新路径，将path[i][j]=path[i][k]
 同时权值邻接矩阵更新`map[i][j]=map[i][k]+map[k][j]
 
for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]+map[k][j]<map[i][j])
                {
                	 map[i][j]=map[i][k]+map[k][j];
                	 path[i][j]=path[i][k];
				}
 
1.5
 输出最短路径的值
 
for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout<<map[i][j]<<" ";
            cout<<endl;
    }
 
1.6
 输出最短路径
 这里我们要输入两个结点v1 v2
 最后输出的就是v1到v2的最短路径
 仔细想想我们的path[v1][v2]储存的是v1 v2的第一个中转节点z的信息
 输出z后，path[z][v2]储存的是z到v2的第一个中转结点
 一个一个输出这些中转结点
 以此类推，直到z为v2的时候，这就是v1到v2的最短路径
 
int v1,v2,z;
    cout<<"输入两个点，输出之间路径"<<endl; 
    cin>>v1>>v2;
    z=path[v1][v2];
    cout<<v1;
    while(z!=v2)
    {
    	cout<<"->"<<z;
    	z=path[z][v2];
	}
	cout<<"->"<<v2;
 
二.测试数据
 

 
 这里的最短距离我直接的输出距离矩阵了
 如果要输出更方便阅读的形式
 也可以在输出那块把代码改一下，可以cout<<"v1到v2的距离为：<<map[v1][v2]<<endl
 我就不多写了
 
##测试数据
 1 2 2
 1 3 1
 2 3 5
 2 4 4
 3 4 5
 4 5 6
 
三.源代码
 
#include<iostream>
using namespace std;
#define max 99999

void fuluoyide(int n,int m)
{
	int map[100][100],t1,t2,t3;
	int path[100][100];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=max;
    //读入边
	cout<<"输入点1到点2的距离"<<endl; 
    for(int i=1; i<=m; i++)
    {
        cin>>t1>>t2>>t3;
        map[t1][t2]=t3;
        map[t2][t1]=t3;
        path[t1][t2]=t2;
    }
    //弗洛伊德(Floyd)核心语句
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]+map[k][j]<map[i][j])
                {
                	 map[i][j]=map[i][k]+map[k][j];
                	 path[i][j]=path[i][k];
				}
                   
    cout<<endl<<"最短距离矩阵为："<<endl; 
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout<<map[i][j]<<" ";
            cout<<endl;
    }
    
    int v1,v2,z;
    cout<<"输入两个点，输出之间路径"<<endl; 
    cin>>v1>>v2;
    z=path[v1][v2];
    cout<<v1;
    while(z!=v2)
    {
    	cout<<"->"<<z;
    	z=path[z][v2];
	}
	cout<<"->"<<v2;  
} 

int main()
{
	cout<<"输入顶点数，边数"<<endl; 
	int n,m;
    cin>>n>>m;//n表示顶点个数，m表示边的条数
    cout<<endl;
    fuluoyide(n,m);
}

 
总体来说 弗洛伊德算法的思想不是很难懂，有一点点暴力求值的感觉，就硬算
 我还写了一篇 dijkstra 求最短路径的算法，也可以看看
 
 
如果帮助到你了，点个赞吧

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x3f3f3f3f
int dis[200];
int vis[200];
int map[200][200];
struct mmm
{
    int x;
    int y;
    int v;
}xxx[200];
void dijkstra(int S,int N)   //S表示start,E表示终点
{
    int i,j;
    dis[S] = 0;              //初始化起始点
    vis[S] = 1;
    for(i=1;i<=N;i++)
    {
        if(vis[i]==0)        //避免自己dis[S]被赋值。
        dis[i]=map[S][i];    //算出所有直达
    }
    for(i=1;i<=N;i++)
    {
      int minn = inf, mini = S;  //minn在新的开始又变成了无穷大
      for(j=1;j<=N;j++)
      {
        if(vis[j]==0&&minn>dis[j])
        {
            minn=dis[j];
            mini=j;
        }
      }                          //第一个for每能定一个最短。
      vis[mini]=1;              //做标记,dis[mini]就定住哪个已经是最短了。
      for(j=1;j<=N;j++)
      {
        if(vis[j]==0)
        {
            if(dis[j]>dis[mini]+map[mini][j])    //第二个for是算转达。
            {                                    // 第n个最短，在最后一次之前已经在不断更新的，所以，每次都是最短比最新的，取最短。


                    dis[j]=dis[mini]+map[mini][j];


            }
        }
      }
    }
}
int main()
{
   int n,m;
   int i,j;
   struct mmm t;
   scanf("%d%d",&n,&m);
   for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
  {
            if(i==j)
 map[i][j]=0;
            else map[i][j]=inf;
         }
    }
   while(m--)
   {
       int i,j,val;
       scanf("%d%d%d",&i,&j,&val);
       map[i][j]=val;
   }
   dijkstra(1,n);
   for(i=1;i<=n;i++)
   {
       xxx[i].v=dis[i];
       xxx[i].y=i;
   }
  for(j=1;j<n;j++)
    for(i=1;i<=n-j;i++)
      if(xxx[i].v>xxx[i+1].v)
  {
      t=xxx[i];
      xxx[i]=xxx[i+1];
      xxx[i+1]=t;
  }
   for(i=2;i<=n;i++)
   {
      if(dis[i]==inf)
      printf("1 %d -1\n",xxx[i].y);
      else
      printf("1 %d %d\n",xxx[i].y,xxx[i].v);
   }
    return 0;
}

相信我，看完之后，你会对BFS有种全新的了解，彻底掌握BFS
 只需要这一篇就足够啦，狗头
 
BFS路径表示
 
广度优先搜索顾名思义就是以迷宫里的无向图某一个点，借助队列，一层一层以该点为中心散开进行搜索，简单的BFS只能显示出最短路径的长度，这里探讨的就是如何实现BFS对最短路径的输出
 
简单的BFS
 
通过队列来实现，找到迷宫的起点（S）入队，出队列里面的队首，把队首上下左右相邻的点入队列，一直重复此操作，直到队列里面的所有元素都出队表示该迷宫不存在解，如果在队清空之前找到终点(T)的话，一层一层的遍历，找到的话就一定是最短路了，但是简单的BFS只能通过输出(now.d+1)来表示最短路的步数长度，不能表示出最短路径到底是什么？
 
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;//地图长宽
string maze[110];//地图
bool vis[110][110];//访问标记数组
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};//方向变化
bool in(int x, int y) {//确保在地图里面
    return 0 <= x && x < n && 0 <= y && y < m;
}
struct node{//定义node类型的结构体
    int x,y,d;//d表示路径
    node(int xx,int yy,int dd){//便于输入结构体里面的值
        x=xx;
        y=yy;
        d=dd;
    }
};
int bfs(int sx,int sy){
    queue<node>q;
    q.push(node(sx,sy,0));//将起点放入
    vis[sx][sy]=true;
    while(!q.empty()){//队列如果不为空继续
        node now=q.front();//找到队首
        q.pop();//队首出队
        for(int i=0;i<4;i++){
            int tx=now.x+dir[i][0];//周围遍历
            int ty=now.y+dir[i][1];
            if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){//在界内且未遍历到
                if(maze[tx][ty]=='T'){//如果是终点，BFS返回完成
                    return now.d+1;
                }else{//如果不是不返回，标记该点入队继续搜索
                    vis[tx][ty]=true;
                    q.push(node(tx,ty,now.d+1));
                }
            }
        }
    }
    return -1;//队空未找到就返回-1表示无解
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    int x, y;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {//找到迷宫的起点
                x = i, y = j;
            }
        }
    }
    cout<<bfs(x,y)<<endl;
    return 0;    
}
 
我下午问了杰哥一下，杰哥给我介绍了两种思路下面的三种方法
 真的杰哥这些思路都是很经典很厉害的思想
 
思路一
 
就直接引用原话啦
 
 我看着杰哥的代码理解了一下，大概意思就是
 1.首先正着从起点进行一遍BFS找到终点，再从终点反正来一遍BFS找到起点
 2.开创俩个数组dis1[N][N]和dis2[N][N]分别用于记录正向搜索每一次的出队时的每一个离起点的层数和反向搜索每一次的出队时的每一个点离起点的层数
 3.此时通过BFS我们已经知道最短路径的长度了，某个点只要能满足
 dis1[x][y]+dis2[x][y]=minrode
 那么这个点就一定是这个迷宫最短路径上面的点
 4.通过这样我们就能知道该迷宫的最短路径表示
 
 代码展示如下：
 
include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;//地图最大宽度 
struct node{
	int x,y;
};
queue<node>que;
int n,m,minrode=0;
int fx,fy;//记录终点的坐标值 
char map[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dis1[N][N];//正向记录层数的数组 
int dis2[N][N];//逆向记录层数的数组 
bool mark[N][N];//用来标记是不是在最短路上 

void BFS(int dis[][N],int sx,int sy){
	
	for(int i=0;i<n;i++)//初始化记录层数的dis数组 
		for(int j=0;j<m;j++)
			dis[i][j]=-1;
	
	while(!que.empty())que.pop();//初始化队列 
	
	que.push((node){sx,sy});//放入起点 
	dis[sx][sy]=0;//(sx,sy)为起点 
	
	while(!que.empty()){
		node cur=que.front();//当前状态
		que.pop();
		for(int i=0;i<4;i++){
			node nxt;
			nxt.x=cur.x+dx[i];
			nxt.y=cur.y+dy[i];
			if(map[nxt.x][nxt.y]=='#'){//墙壁无法通行 
				continue;
			} 
			if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
				if(map[nxt.x][nxt.y]=='T'){
					fx=nxt.x;fy=nxt.y;
					minrode=dis[cur.x][cur.y]+1;
					return ;
				}
				else{
				que.push(nxt); 
				dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;//不断的记录层数
			}
			}
		}
	}	
} 

void Print(int x,int y){//对起点进行上下左右找，满足的mark=true的进行输出
	printf("%d %d\n",x,y);	
	for(int i=0;i<4;i++){//同样的进行遍历判断 
		int nx=x+dx[i];
		int ny=y+dy[i];
		
		if(nx<0||nx>=n||ny<0||ny>=m||map[nx][ny]=='#')continue; 
		
		if(dis1[nx][ny]<dis1[x][y])continue;//***不能往回走不能成环 
		
		if(mark[nx][ny]){
			Print(nx,ny);
			break;//避免输出多条最短路 
		}
	}
}


int main(){
	int qx,qy;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",map[i]);
	}
	for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'S') {//找到迷宫的起点
                qx = i;qy = j;
            }
        }
    }
	BFS(dis1,qx,qy);//正向遍历 
	BFS(dis2,fx,fy);//逆向遍历 
	
	memset(mark,0,sizeof(mark));//初始化最短路径记录数组 
	
	int total=minrode;

	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(dis1[i][j]+dis2[i][j]==total){ 
				mark[i][j]=true;//如果符合的话就是最短路，mark数组该点标记为true 
			}
		}
	}
	
	Print(qx,qy);//调用print函数进行打印mark上面为true的点 
	
	return 0;
}

 
重点来了，关键关键关键！！！
 
if(dis1[nx][ny]<dis1[x][y])continue;//***不能往回走不能成环 
 
这一步真的print函数的重点所在
 为什么能打印满足mark数组等于true的点，我们要知道一个迷宫不只有一条最短路，有很多点都满足这个这个条件，那么万一出现这种成环的情况怎么办？
 
 按照print函数层次遍历的算法，在A点可以会向右跑了，这样根本不是最短路，但是我们知道按照最短的遍历,dis1数组上面符合最短路的下一步的值一定会比这一步要大，我们在这里就可以做出限制条件，这样一方面就避免了往回回溯的可能，也避免了成环跑掉的可能，如果最短路不成环的话,我们也可以对已经打印出来的点进行标记，标记后不能打印，这样也可以实现避免了往回回溯的可能。
 
思路二
 
照片如图
 
 这种思路大概就很像树型结构的寻找父亲，保存此时的坐标的信息和上一个坐标的信息，从终点往回不断的找，找父亲的父亲的父亲…直到起点为止，这样找下来也是一种最短路，像我这样就只能想到一些笨办法
 第一种就是直接建立树，这个树结点不仅保存该点的值，还保存下面儿子的地址和上面父亲结点的地址，这样一来直接就可以通过树来找到了，要写树代码量真的太大了，舍去。。。
 第二种就是建立结构体包含四个值，自己的XY坐标值，父亲的XY坐标值，从结点开始利用父亲的XY值遍历整个序列，看谁的XY和这里的对应就找到了父亲结点，依次进行，但是这样的复杂度太高了吧。。。果断舍去。。。
 好的，下面就介绍杰哥给的几种复杂度低的算法
 
算法一
 
这样怎么说呢，有点类似树的双亲孩子表示法，建立一个数组，里面装着每一个结点，结点后面跟着父亲结点在数组里面的下标值，就是一个结构体数组，通过每一个结点里面的父亲结点在数组里面的下标值就可以找到父亲结点了，通过在数组里面存储下标来回溯，很棒呀。
 
 代码如下：
 
/*Input:默认以(0,0)为起点，(4,4)为终点，随便改一下就行 
5 5
...##
##.##
....#
.##.#
.....*/ 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
struct node{
 int x,y,lastId;
}que[N*N];//最大有N*N个结点，没有墙全是路 

int n,m;
char map[N][N];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
 
 void Print(node cur){
 if(cur.lastId!=-1){ 
  Print(que[cur.lastId]);//递归的算法，先找到第一个结点后输出值
 }
 printf("%d %d\n",cur.x,cur.y);//先找后输出就是顺序，先输出后找就是逆序 
}

int dis[N][N];
void BFS(){
 
 memset(dis,-1,sizeof(dis));
 
 int L=1,R=0;
 que[++R]=(node){0,0,-1};//lastId=-1表示没有父亲 
 dis[0][0]=0;//(0,0)为起点 
 
 while(L<=R){
  node cur=que[L++];//当前状态
  
  for(int i=0;i<4;i++){
   node nxt;
   nxt.x=cur.x+dx[i];
   nxt.y=cur.y+dy[i];
   nxt.lastId=L-1;//当前状态的上一个状态在que数组中的下标为L-1 
   
   if(nxt.x==n-1&&nxt.y==m-1){//(n-1,m-1)为终点 
    Print(nxt);
    return; 
   }
   if(map[nxt.x][nxt.y]=='#'){//无法通行 
    continue;
   } 
   
   if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
    que[++R]=nxt; 
    dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;
   }
  }
 } 
} 

int main(){
 scanf("%d%d",&n,&m);
 for(int i=0;i<n;i++){
  scanf("%s",map[i]);
 }
 BFS();
 return 0;
}
 
算法二
 
我真的有点被这个算法惊讶到了
 利用二维数组可以存储四个值，一般来数二维数组值可以存储三个值(x,y,本身点的信息),但是这里可以使用两个二维数组存储x,y,fx,fy的信息，分而和，和而找，既然知道了这四个信息，我们也就不难去回溯了
 代码如下：
 
#include<queue>//还是和上面一样，(0,0)起点，(n-1,m-1)终点 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;

struct node{
 int x,y;
};

int fax[N][N];
int fay[N][N];
 
queue<node>que;//对列 

int n,m;
char map[N][N];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
 
int dis[N][N];

void Print(int x,int y){
 if(x!=-1&&y!=-1){
  Print(fax[x][y],fay[x][y]);
  printf("%d %d\n",x,y);
 }
}

void BFS(){
 
 memset(dis,-1,sizeof(dis));
 
 que.push((node){0,0});
 dis[0][0]=0;//(0,0)为起点 
 
 fax[0][0]=-1;
 fay[0][0]=-1;
 
 while(!que.empty()){
  node cur=que.front();//当前状态
  que.pop();
  for(int i=0;i<4;i++){
   node nxt;
   nxt.x=cur.x+dx[i];
   nxt.y=cur.y+dy[i];
   
   if(map[nxt.x][nxt.y]=='#'){//无法通行 
    continue;
   } 
   
   if(nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<m&&dis[nxt.x][nxt.y]==-1){
    que.push(nxt); 
    dis[nxt.x][nxt.y]=dis[cur.x][cur.y]+1;
    fax[nxt.x][nxt.y]=cur.x;
    fay[nxt.x][nxt.y]=cur.y;
   }
  }
 } 
} 

int main(){
 scanf("%d%d",&n,&m);
 for(int i=0;i<n;i++){
  scanf("%s",map[i]);
 }
 BFS();
 Print(n-1,m-1);
 return 0;
}
 
其他的简单的BFS一样，最为精华的我展示出来了
 
void Print(int x,int y){
 if(x!=-1&&y!=-1){
  Print(fax[x][y],fay[x][y]);
  printf("%d %d\n",x,y);
 }
}
 
难以言语，分开来，合起来，分开来，再合起来…
 道家的思想，
 **分而治之，和而为之 **
 
嗯嗯，就介绍完啦，你是否got到啦
 
是不是肥肠的斯国一
 
感谢杰哥这么细心的指导
 
我终于也掌握BFS啦
 
哈哈哈哈