Sol dönmədən
İnsanın müəyyən bir labirintdə bir hücrədən digərinə keçməsi lazımdır. Hər bir hərəkətlə o, dörd istiqamətdən birinə (yuxarı, aşağı, sola və ya sağa) bir hücrə hərəkət edə bilər, lakin onun hərəkətinə bəzi məhdudiyyətlər var. Başlanğıc hərəkət istiqamətini sərbəst seçə bilər. Lakin bundan sonra 180° dönmək və sol dönmələr (saat əqrəbi istiqamətinin əksinə 90° dönmələr) qadağandır. Beləliklə, yalnız saat əqrəbi istiqamətində 90° dönmələr icazəlidir. Bundan əlavə, labirintin sərhədlərini tərk etmək qadağandır.
Verilmiş hücrələr arasında ən qısa icazə verilən yolu tapmaq üçün bir proqram yazın.
Giriş verilənləri
Birinci sətirdə labirintin ölçülərini müəyyən edən iki tam ədəd M və N (1 ≤ M, N ≤ 1500) verilir. Sonra labirinti təsvir edən M sətirdə hər biri N simvol olan sətirlər gəlir. "*" simvolu divarı göstərir (müvafiq hücrəyə hərəkət etmək qadağandır), "." - boş hücrə, "S" - insanın əvvəlcə yerləşdiyi hücrə, "D" - çatmalı olduğu hücrə. Başlanğıc və son hücrə boş sayılır və hər biri dəqiq bir dəfə rast gəlinir.
Çıxış verilənləri
Tək bir sətirdə, insanı başlanğıc hücrədən son hücrəyə dönmədən və sol dönmələr etmədən aparacaq ən qısa hərəkət ardıcıllığını müəyyən edən sətiri çıxarın. Bu sətirdə "U" simvolu bir hücrə yuxarı hərəkəti, "D" - aşağı, "L" - sola, "R" - sağa hərəkəti göstərir. Əgər son hücrəyə qaydaları pozmadan çatmaq mümkün deyilsə, "NO SOLUTION" (tırnak işarələri olmadan) mesajını çıxarın.