Անկասելի Ռոբոտը
Ուսանողների մի խումբ մշակում էր ռոբոտ, որը կարող է շարժվել լաբիրինթում: Սակայն ռոբոտն այնքան էլ կատարյալ չէ, քանի որ չի կարող փոխել իր ուղղությունը կամ կանգ առնել, մինչև չհասնի պատի կամ խոչընդոտի: Երբ ռոբոտը սկսում է շարժվել, այն գնում է մինչև տվյալ ուղղությամբ հանդիպի ամենամոտ պատն կամ խոչընդոտը, ապա կարող է ընտրել նոր ուղղություն:
Ձեզ խնդրում են պարզել, թե ինչ է ամենափոքր քանակի քայլերը, որ ռոբոտը պետք է կատարի, որպեսզի
S մեկնարկային դիրքից հասնի E վերջնակետին, և տպել այն հրամանները, որոնք անհրաժեշտ է ուղարկել ռոբոտին այդ նպատակի համար.- L – ձախ շարժվել
- U – վերև շարժվել
- R – աջ շարժվել
- D – ներքև շարժվել
Մուտք
Մուտքի առաջին տողում տրված են երկու թվեր
h և w (2 ≤ h, w ≤ 100), որոնք նշում են ցանցի (լաբիրինթի) բարձրությունը և լայնությունը:Հաջորդ
h տողերը պարունակում են w նիշ, որոնք ներկայացնում են ցանցը..հատակն է
#պատն է
Sմեկնարկային դիրքն է
Eավարտական դիրքն է
Վստահեցվում է, որ ցանցը շրջապատված է պատերով, որպեսզի ռոբոտը չկարողանա դուրս գալ լաբիրինթից:
Ելք
Ծրագիրը պետք է նախ տպի ռոբոտի կողմից սկսած դիրքից ավարտական դիրք հասնելու նվազագույն քայլերի քանակը: Երկրորդ տողում պետք է ընդգրկվեն այն բոլոր հրամանները, որոնք անհրաժեշտ է ուղարկել ռոբոտին: Եթե գոյություն ունեն մի քանի հավասարակշիռ լուծումներ, ծրագիրը կարող է տպել դրանցից որևէ մեկը:
Եթե անհնար է, որ ռոբոտը հասնի վերջնակետին, ծրագիրը պետք է տպի
Impossible:Examples
Input
7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########Output
4
RDLUՀուշում
Սկզբնակետը կարելի է դիտարկել ως հատակ (
.), իսկ վերջնակետը՝ որպես պատ (#):Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB