1923 問題 A: 藍橋杯算法提高VIP-學霸的迷宮
時間限制: 1s
內存限制: 128MB 提交: 3073 解決: 750
題目描述
學霸搶走了大家的作業(yè),班長為了幫同學們找回作業(yè),決定去找學霸決斗。但學霸為了不要別人打擾,住在一個城堡里,城堡外面是一個二維的格子迷宮,要進城堡必須得先通過迷宮。因為班長還有妹子要陪,磨刀不誤砍柴功,他為了節(jié)約時間,從線人那里搞到了迷宮的地圖,準備提前計算最短的路線??墒撬F在正向妹子解釋這件事情,于是就委托你幫他找一條最短的路線。
輸入
第一行兩個整數n, m,為迷宮的長寬。
接下來n行,每行m個數,數之間沒有間隔,為0或1中的一個。0表示這個格子可以通過,1表示不可以。假設你現在已經在迷宮坐標(1,1)的地方,即左上角,迷宮的出口在(n,m)。每次移動時只能向上下左右4個方向移動到另外一個可以通過的格子里,每次移動算一步。數據保證(1,1),(n,m)可以通過。
輸出
第一行一個數為需要的最少步數K。
第二行K個字符,每個字符∈{U,D,L,R},分別表示上下左右。如果有多條長度相同的最短路徑,選擇在此表示方法下字典序最小的一個。
提示
零基礎同學可以先學習
視頻課程,包含C/C++、Python、百練、藍橋杯輔導、算法數據結構等課程,提供視頻講解以及配套習題,還有老師答疑,
點擊這里了解課程詳情