Lesson 5 � Intermediate

Maze & Path Finding Problems

Maze problems recursion + backtracking ka interesting application hain. Grid mein path find karna, word search karna, area fill karna � ye sab real-world problems hain jo backtracking se solve hoti hain. Rat in Maze sabse classic example hai.

? 22 min✓ Intermediate✓ Backtracking framework

Maze Problems kya hain?

WHAT

Maze problems mein ek 2D grid hota hai jismein obstacles hain. Tumhe start se end tak path find karna hai, ya saare paths count karne hain, ya koi specific pattern search karna hai. Har step pe 4 directions (up, down, left, right) mein ja sakte ho.

WHEN

Jab grid mein path find karna ho, jab word grid mein search karna ho, jab connected components find karne ho, jab area calculate karna ho � tab maze problems use karo.

WHERE

Rat in Maze, Unique Paths, Word Search I & II, Flood Fill, Number of Islands, Surrounded Regions � ye sab maze/grid backtracking problems hain.

Mental Model: Imagine karo tum ek labyrinth mein ho. Har junction pe 4 raaste hain. Tum ek pe chalte ho � agar dead end mil jaaye toh peeche aate ho aur doosra try karte ho. Jab exit mil jaaye toh path note karte ho. Maze problems bhi yahi karte hain.

Rat in Maze

Rat in Maze sabse classic maze problem hai. Ek rat (0,0) se (n-1,n-1) tak jaana chahta hai. 1 = open path, 0 = blocked:

# Rat in Maze � Find path from top-left to bottom-right
# 1 = open, 0 = blocked

def solve_maze(maze):
 n = len(maze)
 sol = [[0] * n for _ in range(n)]
 
 if not solve(maze, 0, 0, sol):
 print("No solution exists")
 return
 
 for row in sol:
 print(row)

def solve(maze, x, y, sol):
 n = len(maze)
 
 # Base case: destination pahunch gaye
 if x == n - 1 and y == n - 1:
 sol[x][y] = 1
 return True
 
 # Check: (x, y) safe hai ya nahi
 if is_safe(maze, x, y):
 # CHOOSE: Current cell pe mark karo
 sol[x][y] = 1
 
 # EXPLORE: Neeche jaao
 if solve(maze, x + 1, y, sol):
 return True
 # EXPLORE: Right jaao
 if solve(maze, x, y + 1, sol):
 return True
 
 # UNCHOOSE: Backtrack � path galat tha
 sol[x][y] = 0
 return False
 
 return False

def is_safe(maze, x, y):
 n = len(maze)
 return (x >= 0 and x < n and y >= 0 and y < n
 and maze[x][y] == 1)

# Example
maze = [
 [1, 0, 0, 0],
 [1, 1, 0, 1],
 [0, 1, 0, 0],
 [1, 1, 1, 1]
]
solve_maze(maze)

Key Point: Maze mein sirf 2 directions try karte hain � right aur down. Kyunki agar left ya up jaoge toh infinite loop ho sakta hai. Direction fix karo ya visited[] array use karo.

Unique Paths

M�N grid mein top-left se bottom-right tak kitne unique paths hain✓ Har step pe right ya down ja sakte ho:

# Unique Paths � Count all paths
def unique_paths(m, n):
 def count_paths(x, y):
 # Base case: destination
 if x == m - 1 and y == n - 1:
 return 1
 # Out of bounds
 if x >= m or y >= n:
 return 0
 
 # Right + Down
 return count_paths(x + 1, y) + count_paths(x, y + 1)
 
 return count_paths(0, 0)

print(unique_paths(3, 7)) # 28

# Unique Paths with Obstacles
def unique_paths_with_obstacles(grid):
 m, n = len(grid), len(grid[0])
 
 def count_paths(x, y):
 if x >= m or y >= n or grid[x][y] == 1:
 return 0
 if x == m - 1 and y == n - 1:
 return 1
 
 return count_paths(x + 1, y) + count_paths(x, y + 1)
 
 return count_paths(0, 0)

grid = [
 [0, 0, 0],
 [0, 1, 0],
 [0, 0, 0]
]
print(unique_paths_with_obstacles(grid)) # 2

Word Search in Grid

Ek 2D character grid mein word find karna � har cell se start karke adjacent cells mein search karo:

# Word Search � Find word in grid
def word_search(board, word):
 if not board:
 return False
 
 rows, cols = len(board), len(board[0])
 
 def backtrack(x, y, index):
 # Base case: poora word match ho gaya
 if index == len(word):
 return True
 
 # Check bounds and character match
 if (x < 0 or x >= rows or y < 0 or y >= cols
 or board[x][y] != word[index]):
 return False
 
 # CHOOSE: Visited mark karo
 temp = board[x][y]
 board[x][y] = '#'
 
 # EXPLORE: 4 directions mein jaao
 found = (backtrack(x+1, y, index+1) or
 backtrack(x-1, y, index+1) or
 backtrack(x, y+1, index+1) or
 backtrack(x, y-1, index+1))
 
 # UNCHOOSE: Backtrack
 board[x][y] = temp
 return found
 
 for i in range(rows):
 for j in range(cols):
 if backtrack(i, j, 0):
 return True
 return False

board = [
 ['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']
]
print(word_search(board, "ABCCED")) # True
print(word_search(board, "ABCB")) # False

Flood Fill Algorithm

Flood fill ek start cell se connected saare same-colored cells ko change karta hai � paint bucket tool jaisa:

# Flood Fill � Change connected cells
def flood_fill(image, sr, sc, new_color):
 old_color = image[sr][sc]
 if old_color == new_color:
 return image
 
 def fill(x, y):
 if (x < 0 or x >= len(image) or y < 0 
 or y >= len(image[0]) or image[x][y] != old_color):
 return
 
 image[x][y] = new_color
 fill(x + 1, y)
 fill(x - 1, y)
 fill(x, y + 1)
 fill(x, y - 1)
 
 fill(sr, sc)
 return image

image = [
 [1,1,1],
 [1,1,0],
 [1,0,1]
]
print(flood_fill(image, 1, 1, 2))

Try it: code khud likho

Exercise

Question: 3�3 grid mein top-left se bottom-right tak kitne unique paths hain✓ Sirf number daalo.

Question: Rat in Maze mein kitni directions try hoti hain✓ Sirf number daalo.

Common mistakes

Visited mark nahi karna: Maze mein current cell pe '#' ya visited mark lagao. Nahi toh same cell baar baar visit hoga aur infinite recursion ho jayega.
Backtrack nahi karna: Visited mark hata do jab path galat ho. Nahi toh next path mein woh cell blocked dikhega.
Bounds check bhool jaana: Grid se bahar jaane se pehle x >= 0, x < rows, y >= 0, y < cols check karo.
Sirf 2 directions try karna: Rat in Maze mein right + down sirf tab kaam karta hai jab wapas jaana na pade. Word Search mein 4 directions chahiye.
Same color check nahi karna: Flood Fill mein pehle old_color save karo. Agar new_color == old_color hai toh kuch mat karo � infinite recursion hogi.

Lesson complete?

Maze problems samajh aa gaye✓ Recursion & Backtracking module complete ho gaya! Ab Trees & BST module mein milte hain � wahan recursion aur zyada powerful applications mein dikhega.