🗺️
AI Sketch • మధ్యస్థం⏱️ 19 నిమిషాల పఠన సమయం
మ్యాట్రిక్స్ మరియు గ్రిడ్ సమస్యలు
Grids గా 2D Arrays
Matrix అనేది 2D array, కానీ interviews లో ఇది తరచుగా grid ను సూచిస్తుంది - map, board లేదా maze. ప్రతి cell grid[r][c] ఒక node, దాని neighbors పక్కనే ఉన్న cells.
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
Row r, column c, dimensions m × n. సరళం - కానీ దీని పైన నిర్మించే patterns శక్తివంతమైనవి.
Direction Arrays
నాలుగు వేర్వేరు if-statements రాయడానికి బదులు, direction array ఉపయోగించండి:
# 4-దిశల (పైన, కింద, ఎడమ, కుడి)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
# 8-దిశల (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:
# neighbor ను process చేయి
Grid సమస్యలలో అత్యంత పునర్వినియోగ code snippet ఇది.
🤯
Direction array trick ను కొన్నిసార్లు "delta encoding" అంటారు. Game development, image processing మరియు competitive programming లో - grids ఉపయోగించే చోటల్లా కనిపిస్తుంది.
Grid పై BFS - Maze లో Shortest Path
BFS unweighted grid లో shortest path కనుగొంటుంది. Source నుండి ప్రారంభించి, దూరం 1 వద్ద అన్ని neighbors ను, తర్వాత దూరం 2 వద్ద, ఇలా explore చేయండి.
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
Grid పై DFS - Flood Fill మరియు Islands సంఖ్య
Flood fill (paint bucket tool లాగా): starting cell నుండి అదే రంగు ఉన్న అన్ని connected cells ను మార్చండి. DFS లేదా BFS రెండూ పనిచేస్తాయి.
పాఠం 10 / 100% పూర్తి
Discussion
Sign in to join the discussion