🗺️
AI Sketch • मध्यम⏱️ 19 मिनट पढ़ने का समय
Matrix और Grid Problems
2D Arrays as Grids
Matrix बस एक 2D array है, लेकिन interviews में यह अक्सर grid represent करता है - map, board, या maze। हर cell grid[r][c] एक node है, और उसके neighbours adjacent cells हैं।
grid = [
[1, 1, 0],
[1, 0, 0],
[0, 0, 1]
]
Row r, column c, dimensions m × n। Simple - लेकिन इस पर बने patterns बहुत powerful हैं।
Directional Arrays
चार अलग if-statements लिखने की जगह direction array इस्तेमाल करो:
# 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
Grid problems में यह सबसे reusable snippet है।
🤯
Direction array trick को "delta encoding" भी कहते हैं। Game development, image processing, और competitive programming में - जहाँ भी grids हों, यह दिखता है।
Grid पर BFS - Maze में Shortest Path
BFS unweighted grid में shortest path ढूँढता है। Source से शुरू करो, पहले distance 1 के सब neighbours explore करो, फिर distance 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
Grid पर DFS - Flood Fill और Number of Islands
Flood fill (paint bucket tool जैसा): starting cell से सभी connected same-colour cells बदलो। DFS या BFS दोनों काम करते हैं।
grid scan करो; मिले तो DFS/BFS चलाकर पूरा island visited mark करो, फिर count बढ़ाओ।
पाठ 10 / 100% पूर्ण
Discussion
Sign in to join the discussion