c++小球入洞宽搜无法记录

【题目描述】
小球入洞是一个经典的闯关游戏，在一个n行m列的平面棋盘中有一个小球。棋盘中有些格子是障碍，小球无法经过。有些格子是空洞，当小球到达空洞处就会落下，游戏就成功通关了。空洞有时候不止一个，小球只要落在任意一个空洞就算成功。
这个游戏的得分与小球滚动的格子数有关，为了获得最高分，你需要用最少的步数使小球落到空洞中。
现在给你一个棋盘全部的信息，希望你给出小球用最少步数落到空洞中的对应方案。
注意：虽然输入的给定的棋盘不包括边界，但是可以认为棋盘周围有一圈障碍，小球不会越出边界。
【输入格式】
输入一共n+1行，第一行两个正整数n和m，表示棋盘的行数和列数。
第2到n+1行，每行m个字母，描述棋盘的具体信息，其中'.'代表空格子，'#'代表障碍，'O'代表空洞，'B'代表球。输入保证棋盘上只有一个球。
【输出格式】
输出一行，包括若干个大写字母，描述小球到达空洞的完整移动步骤，其中'U'代表向上走，'D'代表向下走，'L'代表向左走，'R'代表向右走。如果有多种方案，请给出字典序最小的方向。（把所有可行的移动步骤看做字符串，要求输出最短的字符串，如果最短的字符串有多条，需要输出其中字典序最小的）。
【输入输出样例#1】
输入#1

5 5
#....
##..#
.....
.#..#
O#..B

输出#1

LLUULLDD

【输入输出样例#2】
输入#2

10 9
O.......O
#####....
..#...###
###.##...
.....B.#.
#####.##.
.........
#........
#.#######
#....O...

输出#2

LLUURRURRRU

【数据范围】
对于40%的数据，1≤n,m≤10
另有20%的数据，保证最短路径只有一条；
对于100%的数据，1≤n,m≤1000，保证小球一定能落入至少一个空洞。

我的代码用的宽搜，记录不了搜的过程，有没有办法？谢谢
贴一下我的代码：


#include <bits/stdc++.h>
using namespace std;
int n, m, a[1010][1010], vis[1010][1010];
struct node{
    int dep, x, y;
}
void bfs(){
    queue<node> q;
    q.push(node{0, x, y});
    while(q.empty()){
        node now = q.front();
        q.pop();
        if(1 <= now.x && now.x <= n && 1 <= now.y && now.y <= m && vis[now.x][now.y] == 0){
            q.push(node{now.dep + 1, now.x, now.y});
        }
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                if(a[i][j] != '#'){
                    vis[i][j] = 1;
                }
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
        }
    }
    bfs();
    return 0;
}

宽搜是可以做的。
虽然 n*m 达到了 10^6 级别，记录不了小球经过的路径，但是考虑用一个 pre 数组记录每个点，它是从哪个点搜过来的，也就是它最短路径的上一个点，这样只需要一直找 pre 就可以得到最短路径经过了哪些点。
如何处理字典序最小的条件？因为字典序：D<L<R<U 所以对于每个点，当它往相邻的点搜索时，优先往下面搜（D），再往左边搜（L）...以此类推，这样容易发现，对于那些最短距离相同的点来说，先被推入队列的点的最短路径的字典序是最小的，和前面的 pre 结合一下，只需让一个点的 pre 等于第一个搜到它的点，就可以得到字典序最小的最短路径。有多个终点，就取第一个弹出队列的终点即为答案。

这个问题的回答你可以参考下: https://ask.csdn.net/questions/7612102
除此之外, 这篇博客: Educational Codeforces Round 102 (Rated for Div. 2)中的思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+±-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。但是题目要删掉，中间一段，剩下两段，也就是要把两段合并起来。画个图其实更好理解。红色的是所有的操作，绿色的是要删除的操作，第二个曲线就是合并之后的x值变化曲线。由图可知。后面那部分合并过来之后，起点就是前面那部分的终点！这就是关键点。然后前面那部分的区间的最大最小值和当前值都很好维护。难的是后面那部分怎么维护。后面那部分，从后往前维护，每到一个点，都认为这个点是零点，然后计算最大值最小值。因为是反着来，可以发现操作曲线是一个与原操作关于x轴对称的曲线，所以最大值就是最小值，最小值就是最大值。然后最小值就是当前点到最小值的距离，最大值就是当前点到最大值的距离。之所以算距离，是因为，永远认为当前点是0点。所以距离才是真正的最大最小值。部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

c++小球入洞 宽搜无法记录

c++小球入洞宽搜无法记录