Ալգորիթմներ և Տվյալների Կառուցվածքներ

Անկասելի Ռոբոտը

Ուսանողների մի խումբ մշակում էր ռոբոտ, որը կարող է շարժվել լաբիրինթում: Սակայն ռոբոտն այնքան էլ կատարյալ չէ, քանի որ չի կարող փոխել իր ուղղությունը կամ կանգ առնել, մինչև չհասնի պատի կամ խոչընդոտի: Երբ ռոբոտը սկսում է շարժվել, այն գնում է մինչև տվյալ ուղղությամբ հանդիպի ամենամոտ պատն կամ խոչընդոտը, ապա կարող է ընտրել նոր ուղղություն:

Ձեզ խնդրում են պարզել, թե ինչ է ամենափոքր քանակի քայլերը, որ ռոբոտը պետք է կատարի, որպեսզի 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

To check your solution you need to sign in
Sign in to continue