Swim in Rising Water
تحصل على شبكة n × n من الارتفاعات تحتوي على كل عدد من 0 إلى n²-1 مرة واحدة بالضبط، على شكل قائمة من الصفوف. يبدأ هطول المطر عند الزمن 0، وعند الزمن t يكون الماء عند ارتفاع t في كل مكان، لذا تكون كل خلية ارتفاعها t أو أقل مغمورة بالماء. تبدأ في الخلية العلوية اليسرى. يمكنك السباحة من خلية إلى خلية تشترك معها في ضلع عندما تكون كلتاهما مغمورتين بالماء، ولا تستغرق السباحة أي وقت. أعد أقرب وقت يمكنك فيه الوصول إلى الخلية السفلية اليمنى.
الدالة
- gridinteger-2d-array
- الارتفاعات، على شكل قائمة من n صفوف، يحتوي كلٌّ منها على n أعداد
- تُرجعinteger
- أبكر وقت يمكنك فيه الوصول إلى الخلية السفلية اليمنى
القيود
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- تظهر كل قيمة من 0 إلى
n²-1مرة واحدة بالضبط.
أمثلة
- المدخلات
- grid = [[0, 2], [3, 1]]
- المخرجات
- 2
- الشرح
- عبر الخلية العلوية اليمنى، يكون المسار 0، 2، 1، وأعلى خلية فيه هي 2. وعبر الخلية السفلية اليسرى، يكون المسار 0، 3، 1، وأعلى خلية فيه هي 3. عند الزمن 2 يكون المسار الأول تحت الماء، لذا تكون الإجابة 2.
- المدخلات
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- المخرجات
- 16
- الشرح
- عند الزمن 15 يمكنك الوصول إلى الصف العلوي والرقم 5 أسفل نهايته، لكن كل طريق للخروج من تلك المنطقة يمر عبر 16 أو أكثر. النزول مباشرةً على الجانب الأيمن يمر بـ16 ثم 20. أما الانعطاف يسارًا عند 16 والدوران عبر 15 و14 و13 و12 و11 ثم العودة على طول الصف السفلي، فلا يتجاوز 16، لذا فالإجابة هي 16.
- المدخلات
- grid = [[3, 0], [1, 2]]
- المخرجات
- 3
- الشرح
- يبلغ ارتفاع خلية البداية 3، لذا لا يمكنك أن تكون فيها، ولا مغادرتها، قبل الزمن 3. وبحلول ذلك الوقت، تكون الشبكة بأكملها تحت الماء.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
إذا كان من الممكن أن تتكرر الارتفاعات وتصل إلى 10^9، فأيٌّ من أساليبك سيظل يعمل دون تغيير، وما المجال الذي ستجري عليه البحث الثنائي؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لنفترض أنك تعرف مستوى الماء
t. هل يمكنك معرفة ما إذا كان هناك مسار للعبور؟ كيف تتغير الإجابة مع ازديادt؟يحتاج المسار إلى أن تغطي المياه كل خلية فيه، لذا فإن الوقت الذي يحتاجه المسار هو ارتفاع أعلى خلية فيه. تريد المسار بين الزاويتين الذي يكون ارتفاع أعلى خلية فيه أقل ما يمكن.
إما أن تستخدم البحث الثنائي على
tمع ملء المنطقة كاختبار، أو تشغّل خوارزمية ديكسترا باستخدام كومة صغرى، حيث يكون وقت الخلية هو الأكبر بين وقت وصولك إليها وارتفاعها. توقّف عندما تُزال الخلية السفلية اليمنى من الكومة.
الحل
الوقت الذي يحتاجه المسار هو ارتفاع أعلى خلية فيه، لأن الماء يجب أن يغطي كل خلية تمر بها. لذا تتمثل المهمة في إيجاد مسار بين الزاويتين يكون ارتفاع أعلى خلية فيه أقل ما يمكن: أقصر مسار تكون كلفته قيمة أعلى خلية فيه، لا مجموعها. يمكنك رفع مستوى الماء خطوة واحدة في كل مرة والتحقق، أو إجراء بحث ثنائي على مستوى الماء باستخدام الاختبار نفسه، أو تشغيل خوارزمية Dijkstra مع اعتبار أعلى خلية هي الكلفة.
ارفع مستوى الماء خطوةً واحدة في كل مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت مستوى الماء عند t. الخلايا التي يمكنك الوصول إليها هي الخلايا التي لا يزيد ارتفاعها عن t والمتصلة بنقطة البداية عبر خلايا كهذه. ابدأ بعملية ملء متصل واحدة من الزاوية العلوية اليسرى للعثور عليها: أضف نقطة البداية، وأخرج خلية، ثم أضف كل جار غير مزور لا يزيد ارتفاعه عن t. إذا زِيرت الخلية السفلية اليمنى، فهذا يعني أن المستوى t كافٍ.
الإجابة هي أصغر قيمة لـ t تنجح عندها عملية الملء المتصل في الوصول إلى الوجهة. لا يمكن أن تكون أقل من قيمة الزاوية الأعلى، max(grid[0][0], grid[n-1][n-1])، لأن الزاويتين يجب أن تكونا تحت الماء. ابدأ من ذلك المستوى وأضف 1 حتى تنجح عملية الملء. أول مستوى ينجح هو الإجابة، لأن ارتفاع الماء لا يفتح إلا خلايا ولا يغلق أي خلية: فإذا نجح مستوى ما، فستظل المستويات الأعلى ناجحة.
تستغرق كل حالة اختبار O(n²)، وقد يرتفع الماء نحو n² مرة قبل أن يتمكن من الوصول. في شبكة بحجم 100 × 100، يصل ذلك إلى 10^4 مستوى × 10^4 خلية، أي نحو 10^8 زيارة للخلايا. في الاختبارات الكبيرة، تكون قيمتا الزاويتين 0 و1، وتقع الإجابات بين 4,950 و9,998، لذا تُجرى آلاف عمليات الملء المتصل الكاملة قبل ظهور الإجابة.
الخوارزمية
- عيّن
tإلى الارتفاع الأكبر من ارتفاعَي الزاويتين. - نفّذ ملءً تتابعيًا بدءًا من أعلى اليسار عبر الخلايا التي لا يتجاوز ارتفاعها
t، باستخدام مكدّس صريح وعلامة زيارة لكل خلية. - إذا وصل الملء إلى أسفل اليمين، فأعِد
t. - وإلا، أضف 1 إلى
tوأعِد الملء.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return tالبحث الثنائي عن مستوى الماء
الفكرة
للاختبار في النهج الأول بنية مفيدة. فهو يفشل عند كل مستوى أدنى من الإجابة، وينجح عند كل مستوى يبدأ من الإجابة فما فوق. والسؤال الذي تكون إجابته نعم أو لا، وتتغير مرة واحدة من لا إلى نعم، هو ما يعثر عليه البحث الثنائي في عدد لوغاريتمي من المحاولات.
ابحث بين lo، الزاوية الأعلى ارتفاعًا، وhi = n²-1، أعلى خلية، حيث تكون الشبكة بأكملها تحت الماء ويجب أن ينجح الاختبار. اختبر المستوى الأوسط. إذا تمكنت من العبور، فالإجابة لا تتجاوز mid، لذا اجعل hi = mid؛ وإلا فهي أعلى من mid، لذا اجعل lo = mid + 1. عندما يتساويان، يكون ذلك المستوى هو الإجابة.
في مثال 5 × 5، lo = 6 وhi = 24. يفشل المستوى 15 لأن المنطقة العلوية مغلقة، لذا اجعل lo = 16. تنجح المستويات 20 و18 و17 و16 كلها، فينخفض hi إلى 16، وينتهي البحث عند 16 بعد خمس عمليات ملء فيضي.
تحتوي شبكة 100 × 100 على 10^4 مستوى، لذا تحسم الأمر نحو 14 اختبارًا، كلفة كل منها O(n²): أي نحو 1.4 × 10^5 زيارة للخلايا بدلًا من 10^8. اجعل الملء الفيضي تكراريًا. ومن الاختبارات الكبيرة ممر متعرج يبلغ طوله نحو 5,000 خلية، وعمقه أكبر بكثير من حد Python البالغ 1,000 استدعاء متداخل.
الخوارزمية
- عيّن
loإلى ارتفاع الزاوية الأعلى وhiإلىn²-1. - ما دام
lo < hi، احسبmid = (lo + hi) / 2، مع التقريب إلى الأسفل. - نفّذ الملء التدفقي عند المستوى
mid. إذا وصل إلى أسفل اليمين، فعيّنhi = mid؛ وإلا فعيّنlo = mid + 1. - أعِد
lo.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return loخوارزمية ديكسترا على أعلى خلية في المسار
الفكرة
اعتبر الشبكة رسمًا بيانيًا، وأعطِ كل مسار كلفةً تساوي أعلى خلية فيه، لا مجموع خطواته. تظل خوارزمية Dijkstra صالحة مع هذه الكلفة، لأن تمديد المسار لا يجعله أقل كلفة أبدًا. فكلفة المسار الأطول هي max(old cost, new height)، وهي لا تقل أبدًا عن الكلفة القديمة، وهذه هي الخاصية الوحيدة التي تحتاج إليها خوارزمية Dijkstra.
احتفظ بكومة صغرى لخلايا الشبكة، تكون المفاتيح فيها هي أوقاتها، أي أعلى خلية في أفضل مسار عُثر عليه للوصول إليها. ابدأ بالخلية العلوية اليسرى عند الوقت grid[0][0]. أخرج الخلية ذات الوقت الأصغر t؛ ولكل جار لم تزره، حدّد وقته ليكون max(t, its height). عندما تخرج الخلية السفلية اليمنى من الكومة، يكون وقتها هو الإجابة.
يمكنك وضع علامة على الخلية بأنها زِيرت عند دفعها إلى الكومة أول مرة. تخرج الخلايا من الكومة بترتيب أوقاتها، لذا فإن أول خلية تصل إلى جار ما يكون وقتها هو الأصغر بين أوقات جميع الخلايا التي ستصل إليه، ويكون الوقت المحدد لذلك الجار عبرها هو الأفضل الممكن. أما أي مسار يصل لاحقًا فسيكون وقته أكبر أو مساويًا. لذلك تدخل كل خلية الكومة مرة واحدة، بوقتها النهائي.
هذا هو ارتفاع الماء، خطوة بخطوة. تحتوي الكومة على حافة المنطقة التي يمكنك الوصول إليها، وإخراج أدنى خلية منها يعني السماح للماء بالارتفاع بالقدر اللازم تمامًا للوصول إليها. في المثال ذي الشبكة 5 × 5، تكون الخلايا المُخرجة بالترتيب 0، 1، 2، 3، 4، 5، ثم البوابة عند 16. بعد ذلك، يكون وقت كل خلية على الطريق الملتف 16، وتخرج الخلية السفلية اليمنى من الكومة بوقت 16 قبل أي خلية أعلى منها.
تُضاف كل واحدة من الخلايا البالغ عددها n² وتُخرج من الكومة مرة واحدة على الأكثر، بتكلفة O(log n) لكل منها، لذا يكون الزمن O(n² log n)، ويتوقف البحث بمجرد إخراج الخلية المستهدفة.
الخوارزمية
- علِّم الخلية العلوية اليسرى بأنها مُزارَة، وأضِفها مع الزمن
grid[0][0]. - أخرج الخلية ذات أصغر زمن
t. إذا كانت الخلية السفلية اليمنى، فأعِدt. - لكل خلية مجاورة لم تُزَر بعد، علِّمها وأضِفها مع الزمن
max(t, its height). - كرّر بدءًا من الخطوة 2.
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من إغفال زاوية ما، أو جمع التكلفة بدلًا من أخذ القيمة العظمى، أو التوقف عن البحث مبكرًا.
- تجاهل ارتفاع خلية البداية نفسها. لا يمكنك أن تكون في أعلى اليسار قبل أن تغمرها المياه، لذا فإن الإجابة لا تقل عن
grid[0][0]. في حالة[[3, 0], [1, 2]]، الإجابة هي 3. - تجاهل ارتفاع الهدف. يجب أن تُغمر خلية أسفل اليمين أيضًا، لذا فإن الإجابة لا تقل عن
grid[n-1][n-1]. - التحرك جشعًا إلى أقل جار ارتفاعًا للخلية الحالية. قد يتطلب أفضل مسار الصعود إلى بوابة ثم اتخاذ طريق طويل حولها، كما في المثال ذي الحجم 5 × 5. وحده البحث في كامل حدود المنطقة التي وصلت إليها يعثر على ذلك المسار.
- جمع الارتفاعات على طول المسار، كما في مسألة أقصر مسار عادية. الوقت الجديد هو
max(t, height)، وليسt + height. - استخدام الاستدعاء الذاتي لملء المنطقة. قد يمتد مسار متعرج لآلاف الخلايا، ما يتجاوز حد Python البالغ 1,000 استدعاء متداخل.
- التحرك قطريًا. لا يمكنك السباحة إلا إلى خلية تشترك مع خليتك في أحد الأضلاع.
أسئلة شائعة4
ما هو التعقيد الزمني لخوارزمية Swim in Rising Water؟
O(n² log n) باستخدام خوارزمية Dijkstra: تُضاف كل خلية من الخلايا البالغ عددها n² إلى الكومة وتُزال منها مرة واحدة على الأكثر، في كومة تضم حتى n² عنصرًا. للبحث الثنائي في مستوى الماء الحد نفسه، أي نحو log2(n²) عملية لملء المناطق، تستغرق كل منها O(n²). وتستخدم كلتا الطريقتين ذاكرة بحجم O(n²) لعلامات الزيارة وللكومة أو المكدس.
لماذا تعمل خوارزمية ديكسترا عندما تكون التكلفة هي قيمة الخلية الأعلى؟
تتطلب خوارزمية Dijkstra خاصية واحدة: ألا تؤدي إطالة المسار أبدًا إلى خفض تكلفته. هنا تكون التكلفة الجديدة هي max(t, height)، وهي لا تقل أبدًا عن t، لذا تتحقق هذه الخاصية. ولهذا، في المرة الأولى التي تخرج فيها خلية من الكومة، يكون زمنها نهائيًا ويمكنك التوقف عند الهدف.
هل يمكن حل مسألة السباحة في المياه المرتفعة باستخدام البحث الثنائي؟
نعم. إمكانية الوصول إلى الجهة الأخرى عند المستوى t تكون غير متحققة عند كل مستوى أدنى من الإجابة، ومتحققة ابتداءً من الإجابة. ابحث بحثًا ثنائيًا عن t، مستخدمًا ملء المنطقة كاختبار، وستجد الإجابة في نحو log2(n²) اختبارًا: 14 اختبارًا لشبكة بحجم 100 × 100.
هل يمكن لبنية الاتحاد-والإيجاد حل مسألة السباحة في المياه المرتفعة؟
نعم. افتح الخلايا بترتيب ارتفاعها، وصِل كل خلية جديدة بجيرانها المفتوحين، وتوقّف فور أن يصبح الركن العلوي الأيسر والركن السفلي الأيمن ضمن المجموعة نفسها. ارتفاع آخر خلية فتحتها هو الإجابة. بما أن الشبكة تحتوي على كل قيمة من 0 إلى n²-1 مرة واحدة، فإن جدولًا يربط الارتفاع بالخلية يحدّد ترتيب الفتح دون فرز.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def swimInWater(grid):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
grid = [[0, 2], [3, 1]]
المتوقع
2