پیدا کردن مسیر در ماتریس
مساله 9 - صفحه 14 کتاب «مسالههای الگوریتمی»: پیدا کردن مسیر در ماتریس
برنامهای بنویسید تا با دریافت n (1 ≤ n ≤ 100) و ماتریس Pn×n، از اعداد صحیح نامنفی کمتر از 100، مسیری از درایههای مجاور آن پیدا کند که از p1,1 شروع و به pn,n ختم شود و مجموع درایههای آن کمترین باشد. دو درایه در صورتی مجاور خوانده میشود که یا پهلوی هم باشند و یا یکی از آنها زیر دیگری باشد.
حالت اول: فرض کنید حرکت تنها به سمت پایین و یا به سمت راست مجاز باشد. با این شرط برنامهای بنویسید که مسیر مورد نظر را به دست آورد.
حالت دوم: مسئله را بدون شرط فوق حل کنید.
برای هر دو حالت، ابتدا مجموع درایههای بدست آمده، و سپس مختصات نقاط مسیر بدست آمده را به ترتیب بنویسید. به مثال زیر توجه کنید:
|
ورودی نمونه 5
|
خروجی قسمت اول 156 1 1 2 1 2 2 2 3 3 3 3 4 3 5 4 5 5 5 |
خروجی قسمت دوم 141 1 1 2 1 3 1 4 1 4 2 4 3 3 3 3 4 3 5 4 5 5 5 |
برای ماتریس نمونه فوق با احتساب محدودیت گفته شده در قسمت اول سوال، مسیری که با شروع از خانه اول (p1,1) تا خانه آخر (pn,n) میپیماییم و مجموع عددهای مسیر کمترین مقدار ممکن (156) را داراست، درواقع بصورت زیر است:
| 2 | 10 | 31 | 71 | 2 |
| 5 | 23 | 17 | 49 | 52 |
| 12 | 91 | 1 | 11 | 4 |
| 3 | 2 | 8 | 49 | 31 |
| 31 | 11 | 60 | 71 | 62 |
همچنین بدون در نظر گرفتن محدودیت گفته شده در قسمت اول سوال و مطابق خواسته قسمت دوم سوال، مسیری که با شروع از خانه اول (p1,1) تا خانه آخر (pn,n) میپیماییم و مجموع عددهای مسیر کمترین مقدار ممکن (141) را داراست، درواقع بصورت زیر است:
| 2 | 10 | 31 | 71 | 2 |
| 5 | 23 | 17 | 49 | 52 |
| 12 | 91 | 1 | 11 | 4 |
| 3 | 2 | 8 | 49 | 31 |
| 31 | 11 | 60 | 71 | 62 |
تگ ها
- پیشنهادی
- تازهها
- ویژهنامه
