+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده باشید، درمی‌یابید که *همه استفا عاشق مصطفی هستند*. چند روز پیش تولّد مصطفی بود و به همین مناسبت استف‌ها برای او یک ربات به اسم کریم خریدند. کریم در یک زمین بازی مستطیلی به ابعاد $n \times m$ قرار می‌گیرد و یک دنباله از دستورات را دریافت می‌کند و طبق آن‌ها در زمین بازی حرکت می‌کند. دور زمین بازی دیوار کشیده شده است و بعضی از مربّع‌های $1 \times 1$ شامل مانع هستند؛ در صورتی که کریم به دیوار دور زمین یا یکی از این موانع برخورد کند، منفجر می‌شود و مصطفی ناراحت می‌شود. هر دستوری که کریم دریافت می‌کند، با یکی از حروف `D`(حرکت به سمت پایین)، `U`(حرکت به سمت بالا)، `R`(حرکت به سمت راست) یا `L`(حرکت به سمت چپ) نمایش داده می‌شود. بنابراین اگر کریم مجموعه‌ی دستورات `DDRUL` را دریافت کند، ابتدا به اندازه‌ی ۲ خانه (مربّع $1 \times 1$) به پایین می‌رود. سپس یک خانه به راست، یک خانه به بالا و در نهایت یک خانه به چپ می‌رود. مصطفی بسیار ریسک‌پذیر است؛ او به پیشنهاد تیم علمی مبنی بر انجام یک بازی بسیار خطرناک با کریم جواب مثبت داده! بازی سه مرحله دارد. در مرحله‌ی *اوّل*، تیم علمی یک دنباله از دستورات کریم را بیان می‌کنند. در مرحله‌ی *دوم* مصطفی باید کریم را در یکی از $n.m$ خانه‌ی زمین بازی که شامل مانع نیست، قرار دهد. در مرحله‌ی *سوم* نیز، تیم علمی می‌تواند ترتیب دستورات در دنباله‌ای که مشخّص کرده بود را عوض کند. مثلن اگر دنباله‌ی دستورات ابتدایی `RRDDLLUU` باشد، پس از آن که مصطفی کریم را در یکی از خانه‌های زمین بازی قرار داد، تیم علمی می‌تواند دنباله‌ی دستوراتش را به `URLDURLD` تغییر دهد. در مرحله‌ی بعد نیز دنباله‌ی دستورات جدید را به کریم می‌دهیم و کریم طبق آن دستورات شروع به حرکت می‌کند. اگر کریم منفجر شود، مصطفی می‌بازد و ناراحت می‌شود، و در غیر این صورت مصطفی برنده‌ی میدان خواهد شد! می‌دانیم به ازای برخی از دنباله‌های دستورات که تیم علمی در مرحله‌ی اوّل انتخاب می‌کند، مصطفی در مرحله‌ی دوم کریم را هر جای زمین بازی قرار دهد، در مرحله‌ی سوم تیم علمی می‌تواند جابه‌جایی‌های دستورات را طوری انجام دهد که مصطفی ببازد. در بین این دنباله‌های دستورات، طول کوتاه‌ترین دنباله را بیابید. # ورودی در خط اول دو عدد $n$ و $m$ ابعاد جدول به شما داده می‌شود. در هر یک از $n$ خط بعدی، $m$ کاراکتر داده می‌شود. چنان‌چه خانه‌ی $j$ام در سطر $i$ام زمین بازی شامل مانع باشد، کاراکتر $j$امِ خط $i$ام برابر `#` و در غیر این صورت برابر `.` خواهد بود. $$ 1 \le n, m \le 2 \ 000 $$ # خروجی در یک خط طول کوتاه‌ترین دنباله‌ی ممکن با شرایط گفته شده را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 ... ... .## ``` ## خروجی نمونه ۱ ``` 3 ``` به طور مثال دنباله‌ی دستورات `RUU` برای این مثال مطلوب است. ## ورودی نمونه ۲ ``` 3 4 #### .### .#.. ``` ## خروجی نمونه ۲ ``` 2 ```

حل سؤال در بانک سؤالات