牛牛走迷宫【牛客tracker 每日一题】

牛牛走迷宫时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛周末去了游乐园走迷宫。这是一个n ∗ m n*mn∗m大小的01 0101迷宫0 00表示这个位置可以走1 11表示有障碍物不能。走。现在牛牛在起点( 1 , 1 ) (1,1)(1,1),他想要走到终点( n , m ) (n,m)(n,m)。并且如果他能够走到终点的话他想要知道自己是怎么走到终点的。如果可以走到终点因为牛牛比较懒他会先保证走的步数最少又因为牛牛是个追求完美的人如果有多条路径步数一样他会选择走字典序最小的那条。数据保证起点和终点都是0输入描述第一行输入两个数n nn和m mm表示n ∗ m n*mn∗m的迷宫大小。( 2 ≤ n 、 m ≤ 500 ) (2≤n、m≤500)(2≤n、m≤500)接下来n nn行每行m mm个字符字符为0 00或者1 110 00表示可以走1 11表示不能走。输出描述如果牛牛不能走到终点请输出 − 1 -1−1,如果可以走到终点第一行请输出牛牛的最小步数k kk。接下来一行输出一个长度为k的字符串(仅包含′ D ′ 、 ′ L ′ 、 ′ R ′ 、 ′ U ′ D、L、R、U′D′、′L′、′R′、′U′)表示牛牛的路径。(D DD表示向下L LL表示向左R RR表示向右U UU表示向上)示例1输入2 2 01 00输出2 DR说明先向下走再向右走解题思路本题核心是反向广度优先搜索(BFS) 正向贪心遍历同时满足最短路径与字典序最小的双重要求。常规正向BFS难以兼顾字典序规则因此从终点( n , m ) (n,m)(n,m)反向遍历迷宫预处理出每个位置到终点的最短距离保证路径步数最少。随后从起点( 1 , 1 ) (1,1)(1,1)出发严格按照D(下)、L(左)、R(右)、U(上)的字典序优先级检查相邻位置优先选择距离减1的合法点移动逐步拼接路径。若起点无法到达终点则输出 -1否则输出路径长度与方向字符串。算法时间复杂度O ( n m ) O(nm)O(nm)完美适配n , m ≤ 500 n,m≤500n,m≤500的数据规模。总结核心逻辑反向BFS预处理最短距离正向按字典序贪心选路同时满足最短步数、最小字典序。关键操作终点反向BFS计算距离、按指定顺序遍历方向、路径动态拼接。效率保障线性遍历网格无冗余计算高效处理题目最大规模的迷宫。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N505;constll INF1e9;ll n,m;ll d[N][N];charmat[N][N];constll dir[]{1,0,-1,0,1};voidsolve(){cinnm;for(ll i1;in;i)for(ll j1;jm;j){cinmat[i][j];d[i][j]INF;}d[n][m]0;queuearrayll,2Q;Q.push({n,m});while(Q.size()){auto[x,y]Q.front();Q.pop();for(ll i0;i4;i){ll nxxdir[i],nyydir[i1];if(nx1nxnny1nymd[nx][ny]INFmat[nx][ny]0){d[nx][ny]d[x][y]1;Q.push({nx,ny});}}}if(d[1][1]INF){cout-1\n;return;}ll x1,y1;string path;while(x!n||y!m){if(xnd[x1][y]d[x][y]-1)x,path.push_back(D);elseif(y1d[x][y-1]d[x][y]-1)y--,path.push_back(L);elseif(ymd[x][y1]d[x][y]-1)y,path.push_back(R);elseif(x1d[x-1][y]d[x][y]-1)x--,path.push_back(U);}coutpath.size()\n;coutpath\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;while(T--)solve();return0;}