Python DFS Practice 🗺️

Depth-First Search - Grid Exploration

Welcome! Learn how to explore grids using Depth-First Search (DFS) - perfect for mazes, maps, and games!

🎯 What is DFS?

Depth-First Search (DFS) = Explore as far as possible in one direction before trying another direction.

Real-World Examples:

🗺️ Exploring a maze - Go down one path completely before trying another
🎮 Flood fill in paint - Click a spot and color spreads
🏝️ Finding islands - Count separate land masses on a map
🧩 Solving puzzles - Try one move deeply before backtracking

Key Idea: Go DEEP first in one direction, then try other directions.

📊 Understanding Grids (2D Lists)

A grid is a 2D list - a list of lists!

# Simple 3x3 grid
grid = [
    [1, 0, 1],
    [1, 1, 0],
    [0, 1, 1]
]

# Visual representation:
# 1 0 1
# 1 1 0
# 0 1 1

Accessing cells:

grid[0][0]  # Top-left: 1
grid[0][1]  # Top-middle: 0
grid[1][1]  # Center: 1
grid[2][2]  # Bottom-right: 1

# grid[row][col]

Grid dimensions:

rows = len(grid)        # Number of rows: 3
cols = len(grid[0])     # Number of columns: 3

🧭 Moving in a Grid (The 4 Directions)

From any cell, you can move in 4 directions:

     UP (-1, 0)
         ↑
LEFT    [ ]    RIGHT
(-) ←   [X]   → (+)
         ↓
    DOWN (+1, 0)

In code:

# Four directions: up, down, left, right
# (row_change, col_change)
directions = [
    (-1, 0),  # Up: row - 1
    (1, 0),   # Down: row + 1
    (0, -1),  # Left: col - 1
    (0, 1)    # Right: col + 1
]

# To move from current position:
current_row = 1
current_col = 1

for dr, dc in directions:
    new_row = current_row + dr
    new_col = current_col + dc
    print(f"Neighbor at ({new_row}, {new_col})")

✅ Checking Valid Positions

Before visiting a cell, check if it's valid!

def is_valid(grid, row, col):
    rows = len(grid)
    cols = len(grid[0])
    
    # Check boundaries
    if row < 0 or row >= rows:
        return False
    if col < 0 or col >= cols:
        return False
    
    return True

# Example:
grid = [[1, 2], [3, 4]]
print(is_valid(grid, 0, 0))   # True
print(is_valid(grid, -1, 0))  # False (out of bounds)
print(is_valid(grid, 2, 0))   # False (out of bounds)

🔄 How DFS Works on Grids

DFS uses recursion to explore deeply!

The Pattern:

Start at a cell
Mark it as visited
Try ONE direction (e.g., up)
Go DEEP in that direction (recursion!)
When stuck, come back and try next direction
Repeat for all 4 directions

Visual Example:

Grid:        Path DFS takes:
. . . .      1 → 2 → 3 → 4
. # # .          ↓       ↓
. . . .          5 → 6 → 7 → 8
                 ↓           ↓
                 9 → 10→ 11→ 12

Goes deep in one direction before trying others!

📝 Basic DFS Template

def dfs(grid, row, col, visited):
    # Base case 1: Out of bounds?
    if row < 0 or row >= len(grid):
        return
    if col < 0 or col >= len(grid[0]):
        return
    
    # Base case 2: Already visited?
    if (row, col) in visited:
        return
    
    # Base case 3: Is this cell blocked? (example: 0 = blocked)
    if grid[row][col] == 0:
        return
    
    # Mark as visited
    visited.add((row, col))
    print(f"Visiting ({row}, {col})")
    
    # Recursive case: Explore all 4 directions
    dfs(grid, row - 1, col, visited)  # Up
    dfs(grid, row + 1, col, visited)  # Down
    dfs(grid, row, col - 1, visited)  # Left
    dfs(grid, row, col + 1, visited)  # Right

Exercise 1: Print All Connected Cells 🖨️

🎯 Functions 📋 Lists 🔄 Recursion

Your Task: Write a function dfs_print(grid, row, col) that:

Starts at position (row, col)
Prints all cells connected to it (value = 1)
Connected means you can reach by going up/down/left/right
Uses DFS and a visited set

Example:

grid = [
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 1]
]

dfs_print(grid, 0, 0)
# Output:
# (0, 0)
# (0, 1)
# (1, 0)
# These three 1s are connected!

dfs_print(grid, 2, 2)
# Output:
# (2, 2)
# This 1 is alone

Hint: Use the template above, but only explore cells with value 1!

Exercise 2: Count Connected Region 🔢

🎯 Functions ➕ Operators 🔄 Recursion

Your Task: Write a function count_region(grid, row, col) that:

Returns the COUNT of cells in the region starting from (row, col)
A region = all connected 1s

Examples:

grid1 = [
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 1]
]
print(count_region(grid1, 0, 0))  # Output: 3
print(count_region(grid1, 2, 2))  # Output: 1

grid2 = [
    [1, 1, 1],
    [0, 1, 0],
    [1, 1, 1]
]
print(count_region(grid2, 0, 0))  # Output: 7 (all 1s connected!)

Hint: Instead of printing, add 1 and return the sum!

Exercise 3: Can Reach Target? 🎯

🎯 Functions 🔀 Conditionals 🔄 Recursion

Your Task: Write a function can_reach(grid, start_row, start_col, target_row, target_col) that:

Returns True if you can reach target from start
Returns False if blocked by 0s
Can only move through 1s

Examples:

grid = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 1]
]

print(can_reach(grid, 0, 0, 2, 2))  # True
# Path: (0,0)→(1,0)→(1,1)→(1,2)→(2,2)

print(can_reach(grid, 0, 0, 0, 2))  # False
# Blocked by 0 at (0,1)

Hint: Base case - if you reach target, return True!

Exercise 4: Flood Fill 🎨

🎯 Functions 🔄 Recursion 📋 Lists

Your Task: Write a function flood_fill(grid, row, col, new_value) that:

Changes the cell at (row, col) to new_value
Changes ALL connected cells of the same original value
Returns the modified grid
This is how paint bucket works!

Examples:

grid = [
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 1]
]

result = flood_fill(grid, 0, 0, 2)
# Output:
# [2, 2, 0]
# [2, 0, 0]
# [0, 0, 1]
# Connected 1s became 2s!

grid2 = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]

result2 = flood_fill(grid2, 0, 0, 5)
# Output:
# [5, 5, 5]
# [5, 0, 5]
# [5, 5, 5]
# All 1s connected around the 0

Hint:

Save the original value at starting position
If current cell != original value, return
Change current cell to new value
Recursively fill all 4 neighbors

Exercise 5: Count Islands 🏝️

🎯 Functions 🔁 Loops 🔄 Recursion

Your Task: Write a function count_islands(grid) that:

Returns the number of separate islands
An island = connected group of 1s
0s are water

Examples:

grid1 = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1]
]
print(count_islands(grid1))  # Output: 3
# Three separate island groups!

grid2 = [
    [1, 1, 1],
    [0, 1, 0],
    [1, 1, 1]
]
print(count_islands(grid2))  # Output: 1
# All 1s are connected!

grid3 = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
print(count_islands(grid3))  # Output: 0
# No islands, all water

Hint:

Loop through every cell in the grid
When you find an unvisited 1, that's a new island!
Use DFS to mark the entire island as visited
Count each time you start a new DFS

Exercise 6: Largest Island 📏

🎯 Functions ➕ Operators 🔄 Recursion

Your Task: Write a function largest_island(grid) that:

Returns the size of the largest island
Returns 0 if no islands exist

Examples:

grid = [
    [1, 0, 1, 1],
    [1, 0, 1, 0],
    [0, 0, 1, 0]
]
print(largest_island(grid))  # Output: 4
# Right island has 4 connected 1s

grid2 = [
    [1, 1],
    [1, 1]
]
print(largest_island(grid2))  # Output: 4
# One big island!

Hint: Similar to count_islands, but track the size of each island and keep the maximum!

Exercise 7: Perimeter of Island 📐

🎯 Functions ➕ Operators 🔄 Recursion

Your Task: Write a function island_perimeter(grid) that:

Assumes there's exactly ONE island
Returns the perimeter (outside edges) of the island
Each cell has 4 edges, but shared edges don't count!

Examples:

grid1 = [
    [1]
]
print(island_perimeter(grid1))  # Output: 4
# One cell = 4 edges

grid2 = [
    [1, 1]
]
print(island_perimeter(grid2))  # Output: 6
# Two cells share one edge: 4+4-2 = 6

grid3 = [
    [1, 1],
    [1, 1]
]
print(island_perimeter(grid3))  # Output: 8
# Square has 8 outside edges

Hint: For each land cell, count how many of its 4 sides touch water or the edge!

Exercise 8: Surrounded Regions 🔴

🎯 Functions 🔄 Recursion 🔀 Conditionals

Your Task: Write a function capture_regions(grid) that:

Changes all 0s that are completely surrounded by 1s into 1s
0s on the edge can't be surrounded
Returns the modified grid

Examples:

grid = [
    [1, 1, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 1]
]
result = capture_regions(grid)
# Output:
# [1, 1, 1, 1]
# [1, 1, 1, 1]
# [1, 1, 1, 1]
# Middle 0s are surrounded, so they become 1s

grid2 = [
    [1, 1, 1, 1],
    [1, 0, 0, 0],
    [1, 1, 1, 1]
]
result2 = capture_regions(grid2)
# Output: Same as input!
# The 0s touch the edge, so they're not surrounded

Hint:

First, DFS from all edge 0s and mark them as "safe"
Then, change all remaining 0s to 1s

🎮 Maze Problems

Let's apply DFS to maze-solving!

Maze Format:

0 = wall (can't pass)
1 = path (can walk)
Start = top-left (0, 0)
End = bottom-right

Exercise 9: Can Exit Maze? 🚪

🎯 Functions 🔄 Recursion 🔀 Conditionals

Your Task: Write a function can_escape(maze) that:

Returns True if you can reach bottom-right from top-left
Returns False if blocked
Can only walk on 1s

Examples:

maze1 = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 0, 1]
]
print(can_escape(maze1))  # True

maze2 = [
    [1, 0, 1],
    [0, 0, 1],
    [0, 0, 1]
]
print(can_escape(maze2))  # False

Exercise 10: Find Path in Maze 🗺️

🎯 Functions 📋 Lists 🔄 Recursion

Your Task: Write a function find_path(maze) that:

Returns a list of (row, col) coordinates from start to end
Returns empty list if no path exists
Start = (0, 0), End = bottom-right

Example:

maze = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 1]
]
print(find_path(maze))
# Output: [(0,0), (0,1), (1,1), (2,1), (2,2)]

Hint: Pass current path as parameter, add to it as you recurse!

💡 DFS Tips for Grids

Always Check:

# 1. Boundaries
if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
    return

# 2. Visited
if (row, col) in visited:
    return

# 3. Valid cell (depends on problem)
if grid[row][col] == 0:  # Example: 0 is blocked
    return

The Four Directions Pattern:

directions = [(-1,0), (1,0), (0,-1), (0,1)]

for dr, dc in directions:
    new_row = row + dr
    new_col = col + dc
    dfs(grid, new_row, new_col, visited)

Common Mistakes:

❌ Forgetting to mark as visited (infinite recursion!)
❌ Not checking boundaries first (index error!)
❌ Modifying grid during exploration (use visited set!)
❌ Not checking all 4 directions

Debug Checklist:

Am I checking boundaries?
Am I tracking visited cells?
Am I exploring all 4 directions?
Am I handling base cases correctly?
Am I passing visited set through recursion?

🌟 What's Next?

After mastering DFS on grids:

BFS (Breadth-First Search) - Find shortest paths
Advanced DFS - Backtracking, state tracking
Graph problems - Trees, adjacency lists
Dynamic Programming - Optimize recursive solutions

Keep practicing! DFS is fundamental to competitive programming! 🚀

✅ Quick Check

Test your understanding:

How do you access a cell at row 2, col 3?
What are the 4 directions you can move in a grid?
When should you check if a position is valid?
What data structure tracks visited cells?
What's the base case for DFS on grids?

Answers:

grid[2][3]
Up (-1,0), Down (1,0), Left (0,-1), Right (0,1)
Before accessing the cell (to avoid index errors)
A set of (row, col) tuples
Out of bounds, already visited, or invalid cell (like 0)

DFS Practice — Graph Exploration

Python DFS Practice 🗺️

Depth-First Search - Grid Exploration

🎯 What is DFS?

📊 Understanding Grids (2D Lists)

🧭 Moving in a Grid (The 4 Directions)

✅ Checking Valid Positions

🔄 How DFS Works on Grids

📝 Basic DFS Template

Exercise 1: Print All Connected Cells 🖨️

Exercise 2: Count Connected Region 🔢

Exercise 3: Can Reach Target? 🎯

Exercise 4: Flood Fill 🎨

Exercise 5: Count Islands 🏝️

Exercise 6: Largest Island 📏

Exercise 7: Perimeter of Island 📐

Exercise 8: Surrounded Regions 🔴

🎮 Maze Problems

Exercise 9: Can Exit Maze? 🚪

Exercise 10: Find Path in Maze 🗺️

💡 DFS Tips for Grids

🌟 What's Next?

✅ Quick Check