یک جدول $m\times n$ داریم که بعضی خانه‌های آن دیوار هستند. می‌خواهیم از کی خانه به خانه‌ی دیگری برویم. در هر مرحله می‌توانیم از یک خانه به یکی از چهار خانه‌ی مجاور ضلعی آن خانه برویم با یک واحد هزینه؛ و نیز می‌توانیم به یکی از هشت خانه مجاور راسی با هزینه‌ی یک‌و‌نیم برویم.

الگوریتمی ارائه کنید که از مرتبه‌ی $O(mn)$ باشد و کوتاه‌ترین مسیر از مبدا به مقصد را بیابد.

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