學(xué)霸搶走了大家的作業(yè)，班長為了幫同學(xué)們找回作業(yè)，決定去找學(xué)霸決斗。但學(xué)霸為了不要?jiǎng)e人打擾，住在一個(gè)城堡里，城堡外面是一個(gè)二維的格子迷宮，要進(jìn)城堡必須得先通過迷宮。因?yàn)榘嚅L還有妹子要陪，磨刀不誤砍柴功，他為了節(jié)約時(shí)間，從線人那里搞到了迷宮的地圖，準(zhǔn)備提前計(jì)算最短的路線。可是他現(xiàn)在正向妹子解釋這件事情，于是就委托你幫他找一條最短的路線。

第一行兩個(gè)整數(shù)n， m，為迷宮的長寬。
接下來n行，每行m個(gè)數(shù)，數(shù)之間沒有間隔，為0或1中的一個(gè)。0表示這個(gè)格子可以通過，1表示不可以。假設(shè)你現(xiàn)在已經(jīng)在迷宮坐標(biāo)(1,1)的地方，即左上角，迷宮的出口在(n,m)。每次移動(dòng)時(shí)只能向上下左右4個(gè)方向移動(dòng)到另外一個(gè)可以通過的格子里，每次移動(dòng)算一步。數(shù)據(jù)保證(1,1)，(n,m)可以通過。

第一行一個(gè)數(shù)為需要的最少步數(shù)K。
第二行K個(gè)字符，每個(gè)字符∈{U,D,L,R},分別表示上下左右。如果有多條長度相同的最短路徑，選擇在此表示方法下字典序最小的一個(gè)。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯 搜索