记 一种可以记录路径的BFS

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

#define checks(x,y)(x >= 1 && x<=30 && y >= 1 && y <= 50) 
int dx[4] = {1,0,0,-1};
int dy[4] = {0,-1,1,0};
char dr[4]= {'D','L','R','U'};
struct node{
	int x;
	int y;
	
}; 
struct Perv{
	char ch;
	node per;
};
Perv maps[35][55];
bool sta [35][55];

void bfs(int x,int y){
	node st,nt;
	st.x = x;
	st.y = y;
	queue <node> q;
	q.push(st); 
	
	sta[1][1] = true;
	
	while(!q.empty() ){
		st = q.front() ;
		q.pop() ;
		for(int i = 0 ; i < 4;i++){
			nt.x = st.x + dx[i];
			nt.y = st.y + dy[i];
			if(checks(nt.x,nt.y)&& (maps[nt.x][nt.y].ch == '0') && sta[nt.x][nt.y] ==false){
				sta[nt.x][nt.y] = true;
				maps[nt.x][nt.y].per.x = st.x;
				maps[nt.x][nt.y].per.y = st.y;
				q.push(nt); 
			}
		}
		
	}
}
int main(){
	string s ;
	for(int i = 1;i<=30;i++){
		for(int j = 1;j<=50;j++){
			cin>>maps[i][j].ch;
			map[i][j]
		}
	}
	
	  bfs(1,1);
    //因为每个位置都有前驱结点的位置
    //从终点开始遍历每个结点的前驱结点，直到起点结束
    node t = {30,50};
     
    //当两个坐标都为1的时候，循环结束
    while(t.x != 1 || t.y != 1)
    {
        //当前结点减去前驱结点得到的值对应的就是前驱节点移动的方向
        int x = t.x - maps[t.x][t.y].per.x;
        int y = t.y - maps[t.x][t.y].per.y;
        int flag;
        for(int i = 0;i < 4;i++)
        {
            if(x == dx[i] && y == dy[i])
            {
                flag = i;
                break;
            }
        }
        switch(flag)
        {
        case 0:
            s += 'D';
            break;
        case 1:
            s += 'L';
            break;
        case 2:
            s += 'R';
            break;
        case 3:
            s += 'U';
            break;
        }
        //更新结点
        t = maps[t.x][t.y].per;
        //cout << t.x << " " << t.y << endl;
    }
    //将得到的路径翻转输出
    for(int i = s.size() - 1;i >= 0;i--)
    {
        cout << s[i];
    }
	
	
	
	return 0;
}

思路来自题解@节奏的个人主页 - 蓝桥云课

开一个字符串作为线路

给矩阵的每一个点一个位置作为前驱节点；

每次找到下一个可行的点记录该点的前驱节点直到到达终点；

到达终点后从终点开始用前驱节点一步一步找到起点并将终点回到起点的路径记入S中

倒序输出S即可得到起点到终点的路径