🗺️
AI Sketch • متوسط⏱️ 19 دقيقة للقراءة
مسائل المصفوفة والشبكة
المصفوفات ثنائية الأبعاد كشبكات
المصفوفة هي مجرد مصفوفة ثنائية الأبعاد، ولكن في المقابلات غالبًا ما تمثل شبكة - خريطة أو لوحة أو متاهة. كل خلية grid[r][c] هي عقدة، وجيرانها عبارة عن خلايا مجاورة.
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
الصف r، العمود c، الأبعاد m × n. بسيطة - ولكن الأنماط المبنية في الأعلى قوية.
المصفوفات الاتجاهية
بدلًا من كتابة أربع عبارات if منفصلة، استخدم مصفوفة اتجاه:
# 4-directional (up, down, left, right)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
# 8-directional (includes diagonals)
dirs = [(-1,0),(1,0),(0,-1),(0,1),
(-1,-1),(-1,1),(1,-1),(1,1)]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
# process neighbour
هذا هو المقتطف الأكثر قابلية لإعادة الاستخدام في مشاكل الشبكة.
🤯
يُطلق على خدعة مصفوفة الاتجاه أحيانًا اسم "ترميز دلتا". ويظهر في تطوير الألعاب ومعالجة الصور والبرمجة التنافسية - حيث يتم استخدام الشبكات في أي مكان.
BFS على الشبكة - أقصر مسار في المتاهة
يعثر BFS على أقصر مسار في شبكة غير مرجحة. ابدأ من المصدر، واستكشف جميع الجيران على مسافة 1، ثم المسافة 2، وهكذا.
from collections import deque
def shortest_path(grid, start, end):
m, n = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
while q:
r, c, dist = q.popleft()
if (r, c) == end:
return dist
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and (nr,nc) not in visited and grid[nr][nc]==0:
visited.add((nr, nc))
q.append((nr, nc, dist+1))
return -1
DFS على الشبكة - تعبئة الفيضان وعدد الجزر
تعبئة الفيضان (مثل أداة دلو الطلاء): من خلية البداية، قم بتغيير جميع الخلايا المتصلة من نفس اللون. يعمل كل من DFS أو BFS.
عدد الجزر: مسح الشبكة؛ عندما تجد ، قم بتشغيل DFS/BFS لوضع علامة على الجزيرة بأكملها كزيارة، ثم قم بزيادة العدد.
الدرس 10 من 100٪ مكتمل
مناقشة
تسجيل الدخول للانضمام إلى النقاش