2178: 信息学奥赛一本通T1255-迷宫问题（bfs储存路径方法）

解题思路:
因为不知道怎么打印路径所以不会做这道题，看了一些题解才明白，当前位置储存上一个位置，记录是从哪里走来的，然后再倒序寻找前面的坐标。

不过这个倒序寻找太麻烦了，这是我按照题解写的倒序寻找

逻辑还算清楚，但是写起来实在麻烦。

直到我做了这道题1923: 蓝桥杯算法提高VIP-学霸的迷宫，是用的在结构体里放置一个存储数组，数组记录从开始到现在的位置，打印的时候直接遍历输出就可以了。

感觉这道题可以这么做，所以在结构体里放置了一个string（因为string打印方便，存放的时候不需要像数组一样获取长度存储），然后用string记录从0,0到4,4的每一步，然后直接输出。

因为不是简单的bfs找长度，所以我就不解释bfs模板了，详见代码注释。
参考代码:

#include <bits/stdc++.h>
#include <queue>
using namespace std;

const int S=5;

struct node{
	int x,y;
	string s; //存放位置
};

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

bool vis[S][S];
int p[S][S];
queue<node>q;

void bfs(int n,int m){
	q.push(node{0,0}); //开始在0,0处
	
	while(!q.empty()){
		
		node now=q.front();//获取队首位置
		vis[now.x][now.y]=1;
		q.pop();
		
		if(now.x==n-1&&now.y==m-1){
			for(int i=0;i<now.s.size();i+=2){//打印
				cout<<"("<<now.s[i]<<", "<<now.s[i+1]<<")"<<endl;
			}
			cout<<"(4, 4)";//因为不存放自身的位置，所以需要单独打印
			break;
		}
		for(int i=0;i<4;i++){
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>=0&&y>=0&&x<n&&y<m){//不超过数组大小
				if(p[x][y]==0&&vis[x][y]==0){//可以走且没有走过
					vis[x][y]=1;
					node nom=now;//现在num.s已经存放了now.s记录的位置（核心代码）
					nom.x=x;
					nom.y=y;
					nom.s+=now.x+'0';//将上一步的位置坐标新增到s里面（核心代码）
					nom.s+=now.y+'0';
					q.push(nom);
				}
			}	
		}
	}
}

int main()
{
	int n=5,m=5;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)cin>>p[i][j];
	}

	bfs(n,m);
 	return 0;
}

这道题打印的时候需要注意,是英文符号，而且,后面有个空格。

以上。