هذا موضوع من سلسلة مواضيع يمكنك الوصول إليها عبر الرابط

وصف التحدي:

افترض أن لديك متاهة maze في شكل grid أبعاده m * n مثلا على الشكل التالي

1 1 1 G 1 G
1 0 0 1 0 1
G 1 0 1 0 1
1 0 0 1 1 1
1 1 G 1 1 G
1 1 1 0 1 1

حيث 1 ممر يمكن المرور عبره 0 حائط لا يمكن المرور G قطعة ذهب

إذا كنت تقف في أعلى نقطة على اليسار والمخرج النقطة الأسفل على اليمين عليك بإيجاد المسار إلى المخرج مع جمع كل الذهب الحل في المثال

DDDDRRRUUUURRDDDDD

حيث D أسفل Down

R يمين Right

U أعلى Up

L يسار Left

ملاحظات:

  1. هناك مسار للمخرج دائما وقد يكون هناك أكثر من واحد

  2. يمكنك اعتبار الذهب على مسار واحد أي لن تحتاج للعودة إلى نقطة زرتها مسبقا

  3. المدخل دائما النقطة أعلى اليسار والمخرج النقطة أسفل اليمين

المدخلات

أول سطر أبعاد المتاهة ثم تأتي المتاهة مثلا

6 6
1 1 1 G 1 G
1 0 0 1 0 1
G 1 0 1 0 1
1 0 0 1 1 1
1 1 G 1 1 1
1 1 1 0 1 1

المخرجات

المسار للمخرج

 DDDDRRRUUUURRDDDDD

نقاط إضافية Bonus

  1. جد أقصر الطرق لإيجاد المخرج مع جمع الذهب

  2. صمم خوارزمية في حالة الذهب ليس في مسار واحد أي يجب عليك أن تقوم ب backtraking

  3. جد كل المسارات التي يمكن بها حل المتاهة