هذا موضوع من سلسلة مواضيع يمكنك الوصول إليها عبر الرابط
وصف التحدي:
افترض أن لديك متاهة 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
ملاحظات:
هناك مسار للمخرج دائما وقد يكون هناك أكثر من واحد
يمكنك اعتبار الذهب على مسار واحد أي لن تحتاج للعودة إلى نقطة زرتها مسبقا
المدخل دائما النقطة أعلى اليسار والمخرج النقطة أسفل اليمين
المدخلات
أول سطر أبعاد المتاهة ثم تأتي المتاهة مثلا
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
جد أقصر الطرق لإيجاد المخرج مع جمع الذهب
صمم خوارزمية في حالة الذهب ليس في مسار واحد أي يجب عليك أن تقوم ب backtraking
جد كل المسارات التي يمكن بها حل المتاهة
التعليقات