//存储容器：1：node father[maxn][maxn];//当前节点的父节点

2：struct node//***
{
    int x,y,d;
    char pos;//存储D L R U
};

具体存储：

for(int i=0;i<4;i++){int tox=now.x+dix[i];int toy=now.y+diy[i];father[tox][toy].x=tox;father[tox][toy].y=toy;if(i==0)//存储路径father[tx][ty].pos='D';else if(i==1)father[tx][ty].pos='L';else if(i==2)father[tx][ty].pos='R';else if(i==3)father[tx][ty].pos='U';
}

打印：

dfs(29,49);//终点坐标

void dfs(int x,int y)//递归打印
{if(x==0&&y==0)//找到起点开始正向打印路径return;elsedfs(father[x][y].x,father[x][y].y);cout<<father[x][y].pos;//在递归下面 
}

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000char maze[maxn][maxn];//地图 
bool vis[maxn][maxn];//标记
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//D L R U，（以这个顺序走，第一个到达终点的不然是字典序最小，因为走的时候就要求字典序最小） 
//char idr[]={'D','L','R','U'}; //和移动方向配对，方便下方的标记从上一点到当前点所走的方向 
bool in(int x,int y)//坐标算法合理 
{return x<30&&x>=0&&y>=0&&y<50;
}struct node//***
{int x,y,d;char pos;//存储D L R U
};node father[maxn][maxn];//当前节点的父节点
node now,nex;//指向当前和下一个位置void dfs(int x,int y)//递归打印
{if(x==0&&y==0)//找到起点开始正向打印路径return;elsedfs(father[x][y].x,father[x][y].y);cout<<father[x][y].pos;//在递归下面 
}void bfs(int x,int y)//bfs 
{queue<node> q;now.x=x;now.y=y;now.d=0;q.push(now);//起点入队 vis[x][y]=true;//起点标记为访问过 while(!q.empty())//核心 {now=q.front();//拿出队头 q.pop();//拿完了就弹出来if(now.x==29&&now.y==49){//到达终点，结束 break;}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)&&!vis[tx][ty]&&maze[tx][ty]!='1')//判断是否超出范围，是否用过，是否为1{vis[tx][ty]=true;//标记为用过nex.x=tx;nex.y=ty;nex.d=now.d+1;//d其实没必要，统计步数 q.push(nex);//压入队列father[tx][ty].x=now.x;//存储父节点坐标********************father[tx][ty].y=now.y;if(i==0)//存储路径father[tx][ty].pos='D';else if(i==1)father[tx][ty].pos='L';else if(i==2)father[tx][ty].pos='R';else if(i==3)father[tx][ty].pos='U';}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);for(int i=0;i<30;i++){//输入 for(int j=0;j<50;j++){cin>>maze[i][j];}}bfs(0,0);//bfs dfs(29,49);//打印路径return 0;
}

overover~