عد مسارات شبكة مع خلايا محجوبة: جمع الوصول من اليسار والأعلى

ما الذي نعده في الشبكة؟

نريد عدد الطرق المختلفة من خلية بداية إلى خلية نهاية في شبكة مستطيلة، بحيث نتحرك إلى اليمين أو إلى الأسفل فقط، ولا ندخل خلية محجوبة. الطريق تتابع خلايا مع حركات مسموحة بينها؛ اختلاف ترتيب الحركات قد ينتج طريقًا آخر حتى لو كان عدد الخطوات واحدًا. لذلك سؤال العدد يختلف من سؤال إيجاد طريق واحد أو حساب أقصر مسافة بين طرفين.

يعرض CSES مسألة Grid Paths I بهذه الحركات مع خلايا ممنوعة، ويشرح دليل USACO جمع عدد الوصول من جهتين سابقتين. سنطبق هذا المنهج المعروف على مثال مستطيل مؤلف من خمسة أعمدة وأربعة صفوف، ونعد الطرق بأعداد صحيحة كاملة. لا ننقل مثال المصدر أو كوده، ولا نقدم جوابنا بوصفه تسليمًا لمسألة مسابقات لها صيغة مدخلات ومخرجات خاصة.

شبكتنا تعليمية، وليست خريطة شوارع أو توزيع احتمالات لحركة مستخدم. كل طريق مسموح يعد مرة، ولا نعطي وزنًا لزمن الانتقال أو فرصة اختياره. كما أن حصر الحركة في جهتين يجعل كل انتقال يتقدم في الشبكة ولا يعود إلى خلية سابقة؛ هذا الشرط هو الذي يسمح بالحساب بالترتيب الذي سنراجعه.

تعريف المسألة، مرجع الجمع والاعتماد على الحركة السابقة.

أعمدة وصفوف وخليتان محجوبتان

نرقم الأعمدة من صفر إلى أربعة من اليسار إلى اليمين، والصفوف من صفر إلى ثلاثة من الأعلى إلى الأسفل. سنكتب الخلية بالزوج عمود ثم صف، أي س ثم ص في مخططنا، مع ازدياد ص نزولًا. البداية عند صفر وصفر، والنهاية عند أربعة وثلاثة. لا نخلط هذه الأزواج بزوج صف وعمود إذا عرضته مكتبة بترتيب آخر.

الخليتان المحجوبتان هما A عند العمود اثنين والصف واحد، و B عند العمود ثلاثة والصف اثنين. كل الخلايا الأخرى مفتوحة، بما فيها البداية والنهاية. الحجب يعني منع الدخول إلى الخلية بالكامل، وليس إغلاق أحد جوانبها فقط. لو كان السؤال عن حواف محجوبة بدل خلايا، لاحتجنا وصفًا آخر يسمح أو يمنع انتقالًا محددًا بين خليتين.

الصورة الرئيسية تعرض عدد الوصول داخل كل خلية، وتضع علامتين واضحتين في A و B. الرقم صفر في هاتين الخليتين ليس عددًا استنتجناه من فقد مسار بعد الحساب؛ هو تطبيق قاعدة الحجب. وقد يظهر صفر في خلية مفتوحة غير قابلة للوصول أيضًا، لذلك نحفظ خريطة الحجب منفصلة من جدول الأعداد كي نميز سبب الصفر حين نراجعه.

البداية تحمل طريقًا واحدًا

إذا كانت خلية البداية مفتوحة، يوجد طريق واحد يصل إليها دون أي حركة: التتابع الذي يحتويها وحدها. لذلك نحفظ عندها العدد واحدًا، لا صفرًا. هذا لا يقول إننا قطعنا خطوة قبل البداية؛ إنه يحدد حالة البدء التي ستعتمد عليها الخلية المجاورة. لو وضعنا صفرًا في كل خلية دون هذا الأساس، لبقي الجمع كله صفرًا رغم وجود طرق واضحة.

أما إذا كانت البداية محجوبة، فلا يوجد طريق مسموح يبدأ منها في عقدنا، فيكون عدد الوصول صفرًا. وبعدها تعطي قاعدة الجمع صفرًا لكل خلية تحتاج وصولًا من هذه البداية. لذلك نفحص الحجب قبل وضع الواحد، ونميز البداية المفتوحة من قاعدة عامة تقول اجعل أول خانة واحدًا دائمًا بصرف النظر عن البيانات.

شبكة من خلية واحدة فقط توضح الحالة: إذا كانت مفتوحة، فالبداية والنهاية الموضع نفسه، وعد الطرق واحد مع صفر حركات. وإذا كانت محجوبة فالعدد صفر. لا نرفض شبكة الخلية الواحدة لأن العرض أو الارتفاع ليس أكبر من واحد؛ فالأبعاد موجبة والسؤال معرف. هذه مراجعة صغيرة تمنع خلط عدد الطرق بطول الطريق.

لماذا نجمع اليسار والأعلى؟

للوصول إلى خلية مفتوحة غير البداية، لا بد أن تأتي آخر حركة من الخلية التي يسارها أو من الخلية التي فوقها. فالانتقال إلى اليمين يأتي من اليسار، والانتقال إلى الأسفل يأتي من الأعلى. نقسم الطرق بحسب هذه الحركة الأخيرة، ثم نضيف عدد المجموعة الأولى إلى عدد الثانية. كل طريق كامل يملك حركة أخيرة واحدة، فلا يقع في المجموعتين معًا.

يمكن أن تشترك طرق المجموعتين في خلايا سابقة، لكن ذلك لا يجعلها الطريق نفسه؛ تختلف الخليتان السابقتان مباشرة إلى الموضع الحالي. لذلك لا نطرح عددًا عند اجتماع الطرق في خلية واحدة. نعد تتابعات الوصول، لا عدد الخلايا الفريدة التي زارتها جميع الطرق مجتمعة. هذا الفرق يفسر لماذا قد يزيد العدد مع بقاء حجم الشبكة صغيرًا.

إذا كانت الخلية محجوبة نجعل عددها صفرًا، ولا نجمع ثم نسمح للرقم بالمرور منها. وعند حافة الشبكة نعامل الجهة غير الموجودة بوصفها لا تمدنا بأي طريق، أي تساهم بصفر. نملأ الصفوف من الأعلى إلى الأسفل، وكل صف من اليسار إلى اليمين، حتى يكون عدد الجهتين جاهزًا حين تحتاجه الخلية التالية.

الصف الأعلى والحافة اليسرى

في الصف الأعلى من مثالنا جميع الخلايا مفتوحة. البداية تحمل واحدًا، والخلية عند العمود واحد تأتي من يسارها فقط فتأخذ واحدًا. يستمر ذلك عبر الأعمدة التالية، فيكون صف الأعداد الأول واحدًا في جميع الأعمدة الخمسة. لا توجد طرق تأتي من أعلى هذا الصف، ولا نضيف حركة افتراضية خارج حدود الشبكة لزيادة العدد.

والعمود الأيسر كله مفتوح أيضًا؛ كل خلية بعد البداية تأتي من فوقها وحدها، فيبقى العدد واحدًا عبر صفوفه. الطريق إلى خلية على هذه الحافة لا يملك اختيارًا بين اليمين والأسفل قبلها، لأن التحرك يمينًا سيجعله غير قادر على الرجوع إلى العمود صفر. هذه نتيجة شرط الجهتين، لا وصف أن الحافة أقصر طريق في شبكة تسمح بالعودة.

لو حجبنا خلية في منتصف الصف الأعلى، لصارت هي وما بعدها في هذا الصف غير قابلة للوصول من البداية، لأن الجهة العليا غير موجودة والجهة اليسرى توقفت. لكن قد تصل طرق إلى خلية أسفلها من اتجاه آخر إذا سمحت الخلايا المفتوحة. لا نعمم انقطاع حافة واحدة إلى حكم أن الشبكة كلها بلا وصول دون استكمال الجدول.

الصف الثاني يمر حول الحجب

في الصف عند ص واحد، تبدأ الخلية اليسرى بواحد. الخلية عند العمود واحد تجمع واحدًا من اليسار وواحدًا من الأعلى، فيكون عددها اثنين. ثم نصل إلى A عند العمود اثنين، وهي محجوبة، فنضع صفرًا. هذا يمنع المرور عبرها، حتى لو كانت فوقها خلية مفتوحة تحمل عددًا موجبًا أو جاءت إليها طرق من يسارها.

الخلية عند العمود ثلاثة في الصف نفسه تأخذ صفرًا من يسارها المحجوب وواحدًا من الأعلى، فتكون قيمتها واحدًا. هذه حالة مهمة: انقطاع الصف عند A لم يجعل جميع الخلايا التالية صفرًا، لأن طريقًا آخر ينزل من الصف الأعلى إلى ما بعدها. والخلية عند العمود أربعة تجمع هذا الواحد مع واحد آخر من الأعلى، فتأخذ اثنين.

إذن صفنا الثاني يحمل واحدًا واثنين وصفرًا وواحدًا واثنين بالترتيب. نربط كل عدد بالعمود والصف، ولا نقرأ الصفر وكأنه فاصل لم يحسب بعد. عند المراجعة يمكن اختيار الخلية التالية للحجب وتتبع طريقها القادم من الأعلى، فتظهر فائدة فصل الحجب عن عدم الوصول، وتظهر أيضًا ضرورة استعمال الجهتين المسموحتين.

الصف الثالث ثم النهاية بتسعة

الصف عند ص اثنين يبدأ بواحد، ثم الخلية عند العمود واحد تجمع واحدًا من يسارها واثنين من فوقها، فتأخذ ثلاثة. الخلية عند العمود اثنين تجمع ثلاثة من اليسار وصفرًا من A فوقها، فتأخذ ثلاثة أيضًا. ثم نصل إلى B عند العمود ثلاثة ونضع صفرًا للحجب. الخلية الأخيرة في هذا الصف تأخذ اثنين من فوقها وصفرًا من يسارها، فتظل اثنين.

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

هذا التسلسل يبين موضع مساهمة كل جزء في العدد النهائي، دون رسم الطرق كلها فوق الشبكة. لو كتبنا ثمانية في نهاية الجدول لمجرد عدد خلايا طريق معين، نكون قد حسبنا شيئًا آخر. كل طريق في مثالنا يزور ثماني خلايا بما فيها الطرفان، لكن يوجد تسعة تتابعات مختلفة تحقق الحجب واتجاه الحركة.

شاهد واحد والطرق التسعة

طريق واضح يسير على الصف الأعلى إلى العمود أربعة، ثم ينزل ثلاث مرات إلى النهاية. حركاته أربع إلى اليمين ثم ثلاث إلى الأسفل، وهو يتجنب A و B لأن النزول عند العمود الأخير. هذا شاهد يثبت وجود طريق، لكنه لا يثبت أن عدد الطرق واحد. هناك طرق تنزل مبكرًا في العمود الأيسر ثم تسير على الصف السفلي أيضًا.

مثلًا، ثلاثة نزولات ثم أربعة انتقالات يمينًا تعطي شاهدًا آخر، يختلف من الأول رغم أن كلاهما سبع حركات. واثنان إلى الأسفل ثم يمين واحد ثم نزول ثم ثلاثة يمينًا يعطيان ترتيبًا ثالثًا مسموحًا. نحفظ الحركة التالية مع الخلية التي دخلها الطريق كي نراجع الحجب، ولا نعتمد على عدد حروف اليمين والأسفل وحده لقبول أي ترتيب.

في الفحص المستقل عددنا جميع سلاسل الحركات ذات أربع يمينات وثلاث نزولات، وحذفنا أي سلسلة تدخل خلية محجوبة. بقيت تسع سلاسل، وهو عدد النهاية في الجدول. طول كل سلسلة سبع حركات لأن الفرق بين الطرفين ثابت. لا تضيف هذه المساواة في الطول معيارًا يفضل طريقًا بزمن سفر أو كلفة لم نعطها في النموذج.

خمسة وثلاثون طريقًا قبل الحجب

إذا فتحنا A و B وكل الخلايا، يبقى على الطريق أن يرتب أربع حركات يمين وثلاث حركات نزول. نختار مواضع النزولات الثلاث بين سبعة مواضع للحركة، وبعد ذلك تشغل اليمين بقية المواضع. عدد الاختيارات هو خمسة وثلاثون. لم نضف ترتيبًا مستقلًا لكل يمين لأنها حركات من النوع نفسه في هذا العد، وليس لها أسماء تميز واحدة من الأخرى.

يمكن مراجعة هذا العدد بجدول الجمع نفسه على الشبكة المفتوحة؛ تعطي النهاية خمسة وثلاثين. والطريق الواحد يقابل اختيارًا واحدًا لمواضع النزول، فلا نكرر التتابع بسبب تسمية الحركة الأولى أو الثانية. هذا الربط يوضح سؤال العد ويعطي طريقة مستقلة للحالة الخالية من الحجب، بدل استعمال جدول يحتوي خلايا محجوبة ثم تجاهل أثرها.

لكن العدد خمسة وثلاثون لا يصلح مباشرة بعد الحجب. المسارات التي تمر في A أو B لم تعد مسموحة، فنحتاج حذفها أو استعمال قاعدة الصفر في الجدول. ولا يكفي طرح اثنين لأننا حجبنا خليتين؛ الخلية الواحدة قد تمر بها طرق كثيرة. سنحسب تلك المجموعات في مثالنا ونراجع التداخل بينهما قبل الحصول على التسعة.

استبعاد مسارات الخليتين دون طرح مكرر

عدد الطرق المفتوحة التي تمر في A يساوي عدد الوصول إليها مضروبًا في عدد الاستمرار منها إلى النهاية. قبل A نحتاج يمينين ونزولًا واحدًا، ولترتيبها ثلاثة اختيارات. وبعدها نحتاج يمينين ونزولين، ولهما ستة ترتيبات. المجموع المار عبر A إذن ثمانية عشر. ونحسب المرور في B بعشرة ترتيبات قبلها واثنين بعدها، فيكون عشرين.

بعض الطرق يمر في A ثم B معًا. بين الخليتين توجد حركة يمين وحركة نزول بترتيبين، وفي البداية إلى A ثلاثة ترتيبات، ومن B إلى النهاية ترتيبان. لذلك عدد المرور فيهما معًا اثنا عشر. إذا طرحنا الثمانية عشر والعشرين من الخمسة والثلاثين دون تعديل، سنحذف هذه الطرق اثنتي عشرة مرة إضافية، لأنها دخلت مجموعتي الاستبعاد.

نضيف الاثني عشر مرة واحدة، فنحسب خمسة وثلاثين ناقص ثمانية عشر ناقص عشرين زائد اثني عشر، والنتيجة تسعة. توافق النتيجة مع الجدول ومع تعداد السلاسل يراجع مثالنا بثلاث طرائق مختلفة. لا نعد وصف المرور في A و B مصدر احتمال مستقل؛ إنه تقسيم لطرق مؤلفة في شبكة معلومة، مع ضبط التكرار بين مجموعتي المرور.

عرض الرسم بالحجم الكامل

صفر النهاية والبداية ونوع العدد

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

نحسب في مثالنا أعدادًا كاملة دون باقي قسمة. عندئذ عدد النهاية صفر يعني عدم وجود طريق في هذا العقد. أما مرجع CSES فيطلب ناتجًا بباقي قسمة على عدد معين؛ هذا تمثيل حسابي مختلف للعدد الكبير. لا نستعمل باقيًا يساوي صفرًا وحده دليلًا على انعدام الطرق. في مثال توضيحي منفصل، الخمسة والثلاثون طريقًا تعطي باقيًا صفرًا عند القسمة على سبعة، مع وجود الطرق جميعًا.

نكتب نوع العدد بجانب الناتج إذا غيرناه، ولا نعرض باقي قسمة صغيرًا بوصفه العدد الكامل للطرق. كذلك لا نطبع قائمة المسارات ثم نعد عناصرًا حذفت منها شواهد بسبب حد عرض، ونسمي العدد شاملًا. الجدول والتعداد في فحوصنا صغيران ويحسبان العقد نفسه، ولم نغير الحساب إلى تقريب أو عينة من الطرق.

تغيير الحجب يغير نسخة الجدول

إذا فتحنا B وبقينا نحجب A فقط، تكون النهاية سبعة عشر، لأننا حذفنا ثمانية عشر طريقًا من أصل خمسة وثلاثين. وإذا فتحنا A وبقي B وحده محجوبًا، تكون النهاية خمسة عشر. وعند حجب الخليتين معًا يكون العدد تسعة كما حسبنا. هذه ثلاث نسخ مختلفة من الشبكة، ولا يخصها جدول واحد لمجرد أن الأبعاد والبداية والنهاية بقيت نفسها.

تغيير الحجب في موضع قد يؤثر في أعداد وصول لاحقة، لكن لا يعني أن كل خانة تتغير. لذلك نعيد الحساب على النسخة المحددة أو ننفذ تحديثًا يراجع جميع الاعتماديات اللازمة. تنفيذنا البسيط يبني جدولًا جديدًا لكل خريطة حجب، ولم نختبر نظام تحديث جزئي يعدل خانة واحدة ثم يترك الأعداد اللاحقة كأنها ما زالت صحيحة تلقائيًا.

والقائمة المخزنة لخلايا الحجب لا تتضمن حافة خارجة من الشبكة أو إحداثيًا سالبًا. نرفض هذه المدخلات في عقد الفحص بدل تجاهلها بصمت. عرض خمسة وارتفاع أربعة يعنيان أعمدة صفر إلى أربعة وصفوف صفر إلى ثلاثة. أما زوج صف وعمود معكوس فقد يصف خلية أخرى أو يقع خارج المجال، فيجب تثبيت الترقيم قبل حفظ النسخة.

ترتيب الحساب وما لا يحفظه العدد

نمر على كل خلية مرة في بناء الجدول، ونقرأ عددًا من اليسار وآخر من الأعلى إذا وجدا. على مستوى عدد الخلايا، يتناسب العمل والمساحة المحفوظة في تنفيذنا مع العرض مضروبًا في الارتفاع. هذا وصف لعمليات الكود، وليس قياس زمن على جهاز أو ضمانًا أن حساب أعداد صحيحة ضخمة له الكلفة نفسها مهما بلغ حجمها.

جدول الأعداد لا يحفظ قوائم الطرق التسعة كلها. قد نضيف نظامًا لاستعادة شواهد أو لتوليد جميع التتابعات، لكن ذلك مهمة أخرى ومخرجات أكبر من عدد واحد. في التحقق استعملنا تعدادًا مستقلًا لأن شبكات الاختبار صغيرة، وحفظنا سلاسل مثالنا لتوضيح معنى الاختلاف. لا نساوي عدد النهاية بقائمة سوابق واحدة كما نفعل عند إعادة شاهد طريق معين.

وإذا سمحنا باليسار أو الأعلى أو الحركة القطرية، فقد لا تبقى قاعدة الجهتين كافية. العودة تخلق اعتماديات ودورات، والقطر يضيف جهة سابقة أخرى. نحتاج عندئذ تعريفًا جديدًا للطريق ولإعادة الزيارة وطريقة الحساب. هدف المقال محدد بالحركتين المعلنتين، فلا ننقل نجاح جدوله إلى شبكة نقل عامة تسمح بالرجوع ثم نعلن أنها عدت كل طرقها.

مراجعة مستقلة لكل خريطة حجب صغيرة

فحصنا 5050 شبكة صغيرة بعروض من واحد إلى أربعة وارتفاعات من واحد إلى ثلاثة، مع جميع اختيارات الحجب الممكنة لكل حجم. لكل شبكة ولدنا سلاسل الحركات مباشرة دون استعمال جدول الجمع، وتتبعنا الخلايا التي تدخلها كل سلسلة. قارنّا عدد السلاسل الصالحة بعدد النهاية من الجدول، فشملت الفحوص حجب البداية والنهاية والانقطاع والشبكات ذات الصف أو العمود الواحد.

وراجعنا مثال الخمسة في الأربعة مستقلًا، وحفظنا طرقه التسعة وجدول الأعداد وعدد الحالة المفتوحة وطرح مجموعات المرور في A و B. اختبرنا كذلك شبكة الخلية الواحدة ورفض الأبعاد أو إحداثيات الحجب المخالفة. هذه تجارب محدودة على عقد واضح، وليست إثباتًا تجريبيًا لكل برنامج أو تمثيل لشوارع فعلية أو قياس سرعة مقارنة بخوارزميات أخرى.

قبل اعتماد نتيجة جديدة، احفظ الأبعاد وترتيب إحداثيات الخلايا وخريطة الحجب والحركتين والبداية والنهاية. ثم راجع حالة البداية وخانة بعد حجب وخانة النهاية، وحدد هل العدد كامل أم باقي قسمة. ستعرف بذلك ما الذي جمعه الجدول ولماذا لا يكرر الطرق عند التقاء فرعين، ومتى يصبح تغيير سؤال الحركة أو نسخة الحجب سببًا لإعادة الحساب.