ماشین شما در یک پارکینگ به شکل یک جدول ‎$m \times n$‎ پارک شده است. هر خانه از جدول یا توسط یک ماشین پر شده است یا کاملاً خالی است. ماشین شما اکنون در گوشه‌ی بالا و چپ جدول قرار دارد و می‌خواهید آن را از پارکینگ خارج کنید. در هر حرکت می‌توان به یکی از خانه‌های سمت چپ، راست یا پایین رفت در صورتی که آن خانه خالی باشد، ولی مجاز به حرکت به سمت بالا نیستید.

در صورتی که خانه‌ی پایینی خالی نباشد، می‌توانیم راننده‌ی آن ماشین را پیدا کنیم و از او خواهش کنیم که ماشینش را از پارکینگ خارج کند. از آنجا که انتقال ماشین به خانه‌ی سمت چپ و راست در این پارکینگ سخت است، می‌خواهیم هنگام خروج از پارکینگ حداکثر ‎$k$‎ حرکت چپ و راست انجام دهیم. درب خروج پارکینگ درست زیر خانه‌ی گوشه‌ی پایین و سمت راست جدول است.

الگوریتمی از مرتبه‌ی ‎${\cal O}(m n k)$‎ ارائه کنید که مسیری برای ماشین بیابد که شروط مذکور را رعایت کند و کم‌ترین تعداد پیدا کردن راننده را لازم داشته باشد. خروجی الگوریتم دنباله‌ای از اعمال است، هر عمل یا حرکت به چپ، راست یا پایین، و یا پیدا کردن راننده‌ی ماشین پایینی است.

• سوال بعد
• سوال قبل