+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ----- پس از تنش‌های بسیار میان راک (رادین کمونیست)‌ و کاکا (کاوه کاپیتالیست)، این دو فرد با هم وارد جنگ شده‌اند. کاهو یکی از سربازهای ارتش کاکا است و از آنجایی که روحیه جنگجویی ندارد می‌خواهد از میدان جنگ فرار کند. میدان جنگ به شکل یک جدول $n \times n$ است که در تعدادی از خانه های آن مین وجود دارد. کاهو در خانه‌ی گوشه **پایین-چپ** جدول قرار دارد و می‌خواهد به خانه‌ی گوشه **بالا-راست** جدول برود تا از میدان جنگ فرار کند. او در هر لحظه به سمت یکی از چهار جهت بالا، پایین، چپ و راست قرار دارد. کاهو می‌خواهد **پیش از شروع** دنباله‌ای از حرکات را برای خود یادداشت کند تا در هنگام فرار از آن پیروی کند. هر حرکت دنباله به یکی از سه حالت زیر است: + یک واحد در همین جهت به جلو برو. + ۹۰ درجه به سمت راست بچرخ. + ۹۰ درجه به سمت چپ بچرخ. همچنین کاهو آدم عاقلی است بنابراین اگر با پیروی از دستوری از جدول خارج شود، پا بر روی مین بگذارد یا اگر پیش از این دستور به نقطه‌ی پایان رسیده باشد این دستور را اجرا نمی‌کند و سراغ دستور بعدی میرود. **یعنی در هر لحظه ای که کاهو به گوشه بالا-راست جدول رسیده باشد حرکت خود را متوقف می‌کند و دیگر به حرکت ادامه نمی‌دهد.** کاهو میداند پیش از نوشتن یادداشت خود به یکی از دو جهت بالا یا راست بوده، **اما نمی‌داند کدام یک.** او می‌خواهد یادداشت خود را طوری بنویسد که در هر دو حالت جهت اولیه با اجرای دستورات مطابق آن از خانه **پایین-چپ** به خانه **بالا-راست** جدول برسد. منطقا میخواهد تعداد دستوراتی که برای خود می‌نویسد کمینه باشد. شما باید عدد کمینه تعداد دستوراتی که او نیاز دارد بنویسد را بدست بیاورید. # ورودی در خط اول یک عدد $n$ داده می‌شود. سپس در $n$ خط بعدی در خط $i$ ام یک رشته به طول $n$ داده می‌شود که کاراکتر $j$ ام آن وضعیت وجود/عدم‌وجود مین در خانه محل تقاطع سطر $i$ ام از بالا و ستون $j$ از چپ است. کاراکتر `M` نشان‌دهنده وجود مین در این خانه و `K` نشان‌دهنده خالی بودن این خانه است. $$ n \le 20 $$ تضمین شده است مسیری بدون مین از گوشه پایین-چپ به گوشه بالا-راست جدول وجود دارد. # خروجی طول کوتاه‌ترین دستورالعمل که کاهو را به مقصد می‌رساند را خروجی دهید. ## ورودی نمونه ۱ ``` 3 KMK KKK KKK ``` ## خروجی نمونه ۱ ``` 9 ``` یکی از دستورالعمل‌های نمونه «جلو، راست، جلو، جلو، چپ، جلو، چپ، جلو، جلو» است.

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