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

Pacman - Անվտանգ դուրս գալ

Դուք խաղում եք Pacman խաղը։ Գտնվում եք լաբիրինթում, որտեղ շրջում են հրեշներ։ Ձեր նպատակը լաբիրինթոսի սահմանային որևէ վանդակ հասնելն է՝ խուսափելով նույն վանդակում հայտնվել հրեշի հետ։
Յուրաքանչյուր քայլով դուք կարող եք շարժվել որևէ ուղղությամբ (վեր, ձախ, աջ կամ ներքև), և նույն պահին հրեշներն էլ են շարժվում որևէ ուղղությամբ։
Եթե հնարավոր է ապահով դուրս գալ լաբիրինթոսից, պետք է տպեք ձեր անցած ուղին։ Ձեր ռազմավարությունը պետք է գործի նույնիսկ այն դեպքում, երբ հրեշները տեղեկացված են ձեր պլանի մասին։
notion image

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր h և w (1 ≤ h, w ≤ 1000) — լաբիրինթոսի բարձրությունն ու լայնությունը:
Հաջորդ h տողերում յուրաքանչյուրում կա w նիշ, որոնք նկարագրում են լաբիրինթը.
  • . - հատակ
  • # - պատ
  • M - հրեշ
  • Y - ձեր նախնական դիրքը

Ելք

Ելքի առաջին տողում պետք է տպել այն քայլիների քանակը, որն անհրաժեշտ է լաբիրինթոսից դուրս գալու համար, իսկ եթե դա հնարավոր չէ, տպել Impossible:
Եթե ելքը հնարավոր է, հաջորդ տողում պետք է ցուցադրել ցանկացած ճիշտ երթուղի։

Examples

Input

5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######
Output

5
RRDDR

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