هذا موضوع من سلسلة مواضيع يمكنك الوصول إليها عبر الرابط
http://cutt.us/SNC7
وصف التحدي:
افترض أن لديك متاهة 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
-
جد كل المسارات التي يمكن بها حل المتاهة
from حسوب I/O - الأكثر شيوعاً http://ift.tt/2hKdtZV
ليست هناك تعليقات:
إرسال تعليق
دائماً، رأيكم يهمنا،