Swim in Rising Water
لديك شبكة n × n من الارتفاعات، تحتوي على كل عدد من 0 إلى n²-1 مرة واحدة بالضبط. عند الزمن 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، يكون المسار الأول تحت الماء.
- المدخلات
- 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 مرورًا بـ15 و14 و13 و12 و11 والصف السفلي لا يتجاوز 16 مطلقًا.
- المدخلات
- grid = [[3, 0], [1, 2]]
- المخرجات
- 3
- الشرح
- ارتفاع خلية البداية هو 3، لذا لا يمكنك أن تكون فيها ولا أن تغادرها قبل الزمن 3. وبحلول ذلك الوقت، ستكون الشبكة بأكملها تحت الماء.
سؤال إضافي
إذا كان من الممكن أن تتكرر الارتفاعات وأن تصل إلى 10^9، فأيّ من أساليبك سيظل يعمل دون تغيير، وما الذي ستبحث عنه بحثًا ثنائيًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لنفترض أنك تعرف مستوى الماء
t. هل يمكنك معرفة ما إذا كان هناك مسار للعبور؟ كيف تتغير الإجابة كلما زادتt؟يحتاج المسار إلى أن تغطي المياه كل خلية فيه، لذا فإن الزمن الذي يحتاجه المسار هو زمن أعلى خلية فيه. تريد المسار بين الزاويتين الذي يكون أعلى خلية فيه بأقل ارتفاع ممكن.
إما أن تجري بحثًا ثنائيًا على
tباستخدام ملءٍ غامر كاختبار، أو تشغّل خوارزمية Dijkstra باستخدام كومة صغرى، حيث يكون وقت الخلية هو الأكبر بين وقت وصولك إليها وارتفاعها. توقّف عندما تخرج الخلية الموجودة أسفل اليمين من الكومة.
الحل
يحتاج المسار إلى وقت يساوي ارتفاع أعلى خلية فيه، لأن الماء يجب أن يغطي كل خلية تمر بها. لذا ابحث عن مسار بين الزاويتين يكون ارتفاع أعلى خلية فيه هو الأقل: أقصر مسار تكون كلفته القيمة القصوى، لا المجموع. ارفع مستوى الماء خطوةً خطوة، أو استخدم البحث الثنائي عن المستوى، أو شغّل خوارزمية Dijkstra على تلك الكلفة.
ارفع الماء خطوةً واحدةً في كل مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت مستوى الماء t. يحدّد اجتياح واحد من أعلى اليسار، عبر الخلايا التي لا يتجاوز ارتفاعها t، ما إذا كان بالإمكان الوصول إلى أسفل اليمين. ابدأ t عند قيمة الزاوية الأعلى، max(grid[0][0], grid[n-1][n-1])، إذ يجب أن تكون كلتا الزاويتين تحت الماء، ثم أضف 1 حتى يتمكّن الاجتياح من الوصول. ارتفاع الماء لا يفتح إلا مزيدًا من الخلايا، لذا فإن أول مستوى ينجح هو الإجابة.
تستغرق كل عملية اجتياح O(n²)، وقد يرتفع الماء ما يقارب n² مرة: في شبكة 100 × 100، قد نصل إلى 10^4 مستويات × 10^4 خلية، أي نحو 10^8 زيارة للخلايا.
الخوارزمية
- اجعل
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البحث الثنائي عن مستوى الماء
الفكرة
يفشل اختبار التعبئة الفيضيّة عند كل مستوى أدنى من الإجابة، وينجح عند كل مستوى يبدأ من الإجابة وما فوقها. يعثر البحث الثنائي على نقطة التحوّل هذه بين الزاوية الأعلى وn²-1، حيث تكون الشبكة بأكملها تحت الماء.
في المثال ذي الأبعاد 5 × 5، تكون lo = 6 وhi = 24. يفشل المستوى 15، لذا تصبح lo = 16. تنجح المستويات 20 و18 و17 و16 جميعها، وينتهي البحث عند 16 بعد خمس عمليات تعبئة.
تحتوي شبكة 100 × 100 على 10^4 مستويات، لذا تحسمها نحو 14 عملية تعبئة: حوالي 1.4 × 10^5 زيارة للخلايا بدلًا من 10^8.
الخوارزمية
- عيّن
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ديكسترا على أعلى خلية في المسار
الفكرة
أعطِ كل مسار كلفةً تساوي أعلى خلية فيه. تظل خوارزمية دايكسترا صالحة، لأن تمديد مسار إلى خلية ارتفاعها h يكلف max(old cost, h)، ولا يقل أبدًا عن الكلفة القديمة. احتفظ بكومة صغرى من الخلايا، مرتبة حسب ذلك الوقت، وابدأ من أعلى اليسار عند grid[0][0]. عندما تخرج الخلية السفلية اليمنى من الكومة، يكون وقتها هو الإجابة.
يمكنك وضع علامة على الخلية على أنها زِيرت عند دفعها إلى الكومة للمرة الأولى. تخرج الخلايا من الكومة بترتيب الوقت، لذا فإن أول خلية تصل إلى خلية مجاورة تمنحها أصغر وقت ممكن، وتدخل كل خلية الكومة مرة واحدة.
تحتوي الكومة على حافة المنطقة التي يمكنك الوصول إليها، وكل إخراج منها يرفع مستوى الماء بالقدر اللازم تمامًا للانتقال إلى تلك الخلية. في المثال ذي الأبعاد 5 × 5، تكون أوقات الإخراج 0، ثم 1، ثم 2، ثم 3، ثم 4، ثم 5، ثم البوابة عند 16، وتخرج الخلية السفلية اليمنى عند 16.
الخوارزمية
- علِّم الخانة العلوية اليسرى بأنها زِيرت، وادفعها مع الزمن
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]وgrid[n-1][n-1]: في الحالة[[3, 0], [1, 2]]تكون الإجابة 3. - السير جشعًا نحو الجار الأقل ارتفاعًا. قد يتطلب أفضل مسار الصعود إلى بوابة ثم الالتفاف بالطريق الأطول، كما في المثال ذي الشبكة 5 × 5.
- جمع الارتفاعات على طول المسار، كما في أقصر مسار عادي. الوقت الجديد هو
max(t, height)، وليسt + height. - استخدام الاستدعاء الذاتي لملء المنطقة. قد يمتد المسار المتعرج آلاف الخلايا، مما يتجاوز حد Python البالغ 1,000 استدعاء متداخل.
أسئلة شائعة3
ما هو التعقيد الزمني لخوارزمية Swim in Rising Water؟
O(n² log n) باستخدام خوارزمية Dijkstra: تُضاف كل واحدة من الخلايا n² إلى الكومة وتُزال منها مرة واحدة على الأكثر. البحث الثنائي في مستوى الماء له الحد نفسه، أي نحو log2(n²) عملية اجتياح، تستغرق كل منها O(n²). يستخدم كلاهما ذاكرة O(n²).
هل يمكن حل مسألة Can Swim in Rising Water باستخدام البحث الثنائي؟
نعم. إمكانية العبور عند المستوى t تتغير مرة واحدة، من خطأ إلى صحيح، عند الإجابة. يتطلب البحث الثنائي على t استخدام ملءٍ غامر كاختبار نحو log2(n²) مرة، أي 14 مرة لشبكة بحجم 100 × 100.
هل يمكن لبنية الاتحاد-والإيجاد حل مسألة السباحة في المياه المتصاعدة؟
نعم. افتح الخلايا بترتيب ارتفاعها، واربط كل خلية جديدة بجيرانها المفتوحين، وتوقف بمجرد أن يصبح الركنان ضمن المجموعة نفسها. ارتفاع آخر خلية فتحتها هو الإجابة. بما أن كل قيمة من 0 إلى n²-1 تظهر مرة واحدة، فإن جدولًا يربط الارتفاع بالخلية يحدد الترتيب دون فرز.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def swimInWater(grid):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
grid = [[0, 2], [3, 1]]
الإخراج المتوقع
2