سوال ۱۱

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

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