2577. الحد الأدنى من الوقت لزيارة خلية في شبكة

الصعوبة: Hard

المواضيع: صفيف ، بحث عن العرض الأول ، الرسم البياني ، الكومة (قائمة انتظار الأولوية) ، مصفوفة ، أقصر مسار

يتم إعطاؤك شبكة مصفوفة m x n تتكون من غير سالبة من الأعداد الصحيحة حيث تمثل الشبكة [row] [col] أنت تقف في

top-left

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

مثال 1:

الإدخال:

شبكة = [[0،1،3،2] ، [5،1،2،5] ، [4،3،8،6]]

الإخراج:
• 7
شرح:
• أحد المسارات التي يمكننا اتخاذها هي ما يلي: في t = 0 ، نحن على الخلية (0،0).
• في t = 1 ، ننتقل إلى الخلية (0،1). هذا ممكن لأن الشبكة [0] [1] في t = 2 ، ننتقل إلى الخلية (1،1). هذا ممكن لأن الشبكة [1] [1]
• في t = 3 ، ننتقل إلى الخلية (1،2). هذا ممكن لأن الشبكة [1] [2]
• في t = 4 ، ننتقل إلى الخلية (1،1). هذا ممكن لأن الشبكة [1] [1]
• في t = 5 ، ننتقل إلى الخلية (1،2). هذا ممكن لأن الشبكة [1] [2]
• في t = 6 ، ننتقل إلى الخلية (1،3). هذا ممكن لأن الشبكة [1] [3]
• في t = 7 ، ننتقل إلى الخلية (2،3). هذا ممكن لأن الشبكة [2] [3]
• الوقت الأخير هو 7. يمكن إثبات أنه هو الحد الأدنى للوقت الممكن.
• مثال 2:

الإدخال:

شبكة = [[0،2،4] ، [3،2،1] ، [1،0،4]]

الإخراج:
• -1
شرح:
• لا يوجد مسار من أعلى اليسار إلى الخلية السفلية اليمنى.
• قيود:

m == grid.length

n == شبكة [i] .Length

2

4 sup> 5

0 sup> 5

شبكة [0] [0] == 0

تَلمِيح:

حاول استخدام بعض الخوارزمية التي يمكن أن تجد أقصر المسارات على رسم بياني.

فكر في الحالة التي يتعين عليك فيها الذهاب ذهابًا وإيابًا بين خليتين من المصفوفة لفتح بعض الخلايا الأخرى.

1. حل:
يمكننا تطبيق نسخة معدلة من خوارزمية

Dijkstra

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

يقترب:

تمثيل الرسم البياني

: علاج كل خلية في الشبكة كعقدة. الحواف هي الخلايا المجاورة (لأعلى ، أسفل ، يسار ، يمين) التي يمكنك الانتقال إليها.

1. قائمة انتظار الأولوية (min-heap) : استخدم قائمة انتظار أولوية لاستكشاف الخلية دائمًا بأقل وقت مطلوب. هذا يضمن أننا نعالج الخلايا من أجل أقرب وقت يمكننا فيه الوصول إليها.

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

3. الخروج المبكر : بمجرد أن نصل إلى الخلية اليسرى السفلية ، يمكننا إعادة الوقت. إذا استنفدنا قائمة الانتظار دون الوصول إليها ، فأعود -1.

4. دعنا ننفذ هذا الحل في PHP:

   2577. الحد الأدنى من الوقت لزيارة خلية في شبكة

توضيح:

:

يتم استخدام splpriorityqueue لضمان معالجة الخلايا التي لديها الحد الأدنى للوقت أولاً. يتم تخزين الأولوية في الوقت المناسب لأن splpriorityqueue من PHP هو أقصى درج الافتراضي.

1. بدءًا من الخلية العلوية اليسرى (0 ، 0) ، تقوم الخوارزمية بمعالجة جميع الخلايا القابلة للوصول ، مع الأخذ في الاعتبار الوقت المبكر لكل منها (أقصى (0 ، شبكة [NewRow] [Newcol] - (الوقت 1))).
   
   

زار الخلايا
2. :

   تتبع مجموعة زيارة الخلايا التي تمت معالجتها بالفعل لتجنب الحسابات الزائدة والحلقات اللانهائية.
   
   

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

3. 
   حساب الوقت
   :

تستغرق كل خطوة ثانية واحدة ، وإذا كانت الخلية تتطلب الانتظار (أي الشبكة [NewRow] [Newcol]> الوقت 1) ، تنتظر الخوارزمية حتى الوقت المطلوب.

4. 
   حالة الحافة
   :

إذا تم استنفاد قائمة الانتظار ولم يتم الوصول إلى الخلية السفلية اليمنى ، فإن الوظيفة تعود -1.

5. 
   تحليل التعقيد
   

6. تعقيد الوقت :
   
   تتم إضافة كل خلية إلى قائمة انتظار الأولوية مرة واحدة على الأكثر:

o (m x n x log (m x n))

---

، حيث

1. تعقيد الفضاء :

   • مساحة قائمة انتظار الأولوية والمصفوفة التي تمت زيارتها هي o (m x n) . يدير مثال مدخل:
   $ grid = [ [0 ، 1 ، 3 ، 2] ، [5 ، 1 ، 2 ، 5] ، [4 ، 3 ، 8 ، 6] ] ؛ صدى الحد الأدنى (الشبكة $) ؛ // الإخراج: 7
2. مدخل:

   $ grid = [ [0 ، 2 ، 4] ، [3 ، 2 ، 1] ، [1 ، 0 ، 4] ] ؛ صدى الحد الأدنى (الشبكة $) ؛ // الإخراج: -1

   هذا الحل فعال ويعمل بشكل جيد ضمن القيود.
   • ارتباطات الاتصال إذا وجدت هذه السلسلة مفيدة ، فيرجى التفكير في إعطاء المستودع
   إن دعمك يعني الكثير بالنسبة لي!
إذا كنت تريد المزيد من المحتوى المفيد مثل هذا ، فلا تتردد في متابعتي:

---

LinkedIn

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

github

$grid = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid); // Output: -1