Unit 13 — Grids, Graphs & Traversal

What is the fewest number of steps through a maze? How many separate rooms are connected? Both questions get easier when we treat each open location as a NODE and each allowed move as an EDGE. This unit represents those connections and traverses them without getting stuck in cycles — using parallel arrays, a deque, recursion, and a visited set. Each idea is a short executable demo with a Notice, then a full stdin solver.

You will learn

Visit the four neighbours of a grid cell with correct bounds checks.
Store a graph as an adjacency-list dictionary and read a node's degree.
Flood-fill a region and find the fewest steps with breadth-first search (BFS).
Test whether one node can reach another with depth-first search (DFS).

Lesson 1 — Four Neighbours in a Grid; an Adjacency List

Store a grid as a list of strings. A cell (r, c) has up to FOUR neighbours; add the dr/dc offsets and guard the bounds with 0 <= nr and nr < rows.

grid = ["....", ".##.", "...."]
rows = 3
cols = 4
r = 1
c = 0
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
count = 0
direction = 0
while direction < 4:
    nr = r + dr[direction]
    nc = c + dc[direction]
    if 0 <= nr and nr < rows and 0 <= nc and nc < cols:
        if grid[nr][nc] == ".":
            count = count + 1
    direction = direction + 1
print("open neighbours:", count)

Output

open neighbours: 2

Notice

The four offsets (-1,0),(1,0),(0,-1),(0,1) reach up/down/left/right; only in-bounds open (.) cells count.

A general graph is an ADJACENCY LIST — a plain dict mapping each node to its neighbour list. Undirected edges add BOTH directions.

edges = [(1, 2), (2, 3), (2, 4)]
adj = {}
for pair in edges:
    u = pair[0]
    v = pair[1]
    if u not in adj:
        adj[u] = []
    if v not in adj:
        adj[v] = []
    adj[u].append(v)
    adj[v].append(u)
print(adj)

Output

{1: [2], 2: [1, 3, 4], 3: [2], 4: [2]}

Notice

if u not in adj: adj[u] = [] creates the list on first sight; each edge appends to both endpoints (no defaultdict).

Read a node's neighbours and its degree straight from the dict.

adj = {}
adj[2] = [1, 3, 4]
node = 2
print("neighbours:", adj[node])
print("degree:", len(adj[node]))

Output

neighbours: [1, 3, 4]
degree: 3

Notice

adj[node] is the neighbour list; len(adj[node]) is the degree.

Put it together: the program reads E edges then a query node, builds the adjacency list, and prints the node's degree.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
edges = int(tokens[0])
adj = {}
position = 1
i = 0
while i < edges:
    u = int(tokens[position])
    v = int(tokens[position + 1])
    if u not in adj:
        adj[u] = []
    if v not in adj:
        adj[v] = []
    adj[u].append(v)
    adj[v].append(u)
    position = position + 2
    i = i + 1
node = int(tokens[position])
print(str(len(adj[node])))

Run the full solver from this unit folder:

python assets/l1.py < assets/l1/1.in

Notice

Build the undirected adjacency dict, then print len(adj[node]).

Complexity: O(E) — one pass over the edges.

Lesson 2 — Recursive Flood-Fill & Breadth-First Search

FLOOD-FILL a region: recurse to the 4 neighbours, using a visited set (passed down) and base-casing bounds / walls (#) / already-visited.

grid = ["..#.", ".##.", "...."]
rows = 3
cols = 4
visited = set()

def fill(r, c, visited):
    if not (0 <= r and r < rows and 0 <= c and c < cols):
        return
    if grid[r][c] == "#" or (r, c) in visited:
        return
    visited.add((r, c))
    fill(r - 1, c, visited)
    fill(r + 1, c, visited)
    fill(r, c - 1, visited)
    fill(r, c + 1, visited)

fill(0, 0, visited)
print("region size:", len(visited))

Output

region size: 9

Notice

fill marks the cell then recurses in all four directions; the visited set (an argument) stops cycles and counts the region.

A deque is a FIFO QUEUE: append to enqueue, popleft to dequeue (the OLDEST) — the order that makes BFS find the FEWEST steps.

from collections import deque
queue = deque()
queue.append("A")
queue.append("B")
print("dequeue:", queue.popleft())
print("dequeue:", queue.popleft())
print("empty?", len(queue) == 0)

Output

dequeue: A
dequeue: B
empty? True

Notice

popleft removes the oldest item (A before B); len(queue) == 0 tests empty. (A stack's pop would take the NEWEST — wrong for shortest paths.)

BFS explores layer by layer, recording a distance dict; the first time it reaches a cell is via a SHORTEST path.

from collections import deque
grid = ["...", ".#.", "..."]
rows = 3
cols = 3
start = (0, 0)
queue = deque()
queue.append(start)
distance = {start: 0}
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
while len(queue) > 0:
    current = queue.popleft()
    direction = 0
    while direction < 4:
        nr = current[0] + dr[direction]
        nc = current[1] + dc[direction]
        if 0 <= nr and nr < rows and 0 <= nc and nc < cols:
            cell = (nr, nc)
            if grid[nr][nc] != "#" and cell not in distance:
                distance[cell] = distance[current] + 1
                queue.append(cell)
        direction = direction + 1
print("distance to (2, 2):", distance[(2, 2)])

Output

distance to (2, 2): 4

Notice

BFS around the wall reaches (2, 2) in 4 steps — the fewest. Using a stack (LIFO) instead could report a longer path.

Put it together: the maze program reads the grid with S/T, BFS-searches from S, and prints the fewest steps to T (or -1).

Try it yourself

from collections import deque
import sys

data = sys.stdin.read()
tokens = data.split()
rows = int(tokens[0])
cols = int(tokens[1])
grid = []
start = (-1, -1)
target = (-1, -1)
r = 0
while r < rows:
    row = tokens[r + 2]
    grid.append(row)
    c = 0
    while c < cols:
        if row[c] == "S":
            start = (r, c)
        elif row[c] == "T":
            target = (r, c)
        c = c + 1
    r = r + 1
queue = deque()
queue.append(start)
visited = {start}
distance = {start: 0}
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
answer = "-1"
while len(queue) > 0 and answer == "-1":
    current = queue.popleft()
    if current == target:
        answer = str(distance[current])
    else:
        direction = 0
        while direction < 4:
            nr = current[0] + dr[direction]
            nc = current[1] + dc[direction]
            if 0 <= nr and nr < rows and 0 <= nc and nc < cols:
                next_cell = (nr, nc)
                if grid[nr][nc] != "#" and next_cell not in visited:
                    visited.add(next_cell)
                    distance[next_cell] = distance[current] + 1
                    queue.append(next_cell)
            direction = direction + 1
print(answer)

Run the full solver from this unit folder:

python assets/l2.py < assets/l2/1.in

Notice

BFS with a deque: enqueue neighbours with a distance one more than the current; the FIFO order guarantees the first arrival at T is shortest.

Complexity: O(R*C) — each cell enqueued once.

Lesson 3 — Depth-First Search Reachability

DFS goes as DEEP as possible before backing up. Recurse into unvisited neighbours, marking a visited set passed as an argument.

adj = {}
adj[1] = [2, 3]
adj[2] = [1]
adj[3] = [1, 4]
adj[4] = [3]
visited = set()

def dfs(node, visited):
    visited.add(node)
    i = 0
    while i < len(adj[node]):
        neighbour = adj[node][i]
        if neighbour not in visited:
            dfs(neighbour, visited)
        i = i + 1

dfs(1, visited)
print("nodes reached:", len(visited))

Output

nodes reached: 4

Notice

dfs marks each node and recurses into unvisited neighbours; len(visited) counts everything reachable from the start.

After a DFS from the start, the visited set holds EVERY node reachable from it — so "can we reach X?" is just X in visited.

adj = {}
adj[1] = [2, 3]
adj[2] = [1]
adj[3] = [1]
adj[4] = [5]
adj[5] = [4]
visited = set()

def dfs(node, visited):
    visited.add(node)
    i = 0
    while i < len(adj[node]):
        neighbour = adj[node][i]
        if neighbour not in visited:
            dfs(neighbour, visited)
        i = i + 1

dfs(1, visited)
print(3 in visited)
print(4 in visited)

Output

True
False

Notice

This graph has two separate groups; a DFS from 1 fills visited with {1, 2, 3}, so 3 in visited is True but 4 in visited is False — node 4 lives in a different group and is not reachable.

SHORT-CIRCUIT: stop and return True the moment the target is found.

adj = {}
adj[1] = [2, 3]
adj[2] = [1]
adj[3] = [1, 4]
adj[4] = [3]

def reaches(node, target, visited):
    if node == target:
        return True
    visited.add(node)
    i = 0
    while i < len(adj[node]):
        neighbour = adj[node][i]
        if neighbour not in visited:
            if reaches(neighbour, target, visited):
                return True
        i = i + 1
    return False

print(reaches(1, 4, set()))

Output

True

Notice

reaches(1, 4, ...) is True via 1 → 3 → 4; returning as soon as the target is hit avoids exploring the rest.

Put it together: the reachability program reads E edges then start target, and prints YES if target is reachable from start, else NO.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
edges = int(tokens[0])
adj = {}
position = 1
i = 0
while i < edges:
    u = int(tokens[position])
    v = int(tokens[position + 1])
    if u not in adj:
        adj[u] = []
    if v not in adj:
        adj[v] = []
    adj[u].append(v)
    adj[v].append(u)
    position = position + 2
    i = i + 1
start = int(tokens[position])
target = int(tokens[position + 1])
visited = set()

def reaches(node, target, visited):
    if node == target:
        return True
    visited.add(node)
    neighbours = adj.get(node, [])
    i = 0
    while i < len(neighbours):
        next_node = neighbours[i]
        if next_node not in visited:
            if reaches(next_node, target, visited):
                return True
        i = i + 1
    return False

if reaches(start, target, visited):
    print("YES")
else:
    print("NO")

Run the full solver from this unit folder:

python assets/l3.py < assets/l3/1.in

Notice

Recursive DFS over the adjacency list with a visited set (an argument); short-circuit YES when the target is reached.

Complexity: O(V + E) — each node and edge visited once.

Traversal Checklist

(1) Grid → 4 neighbours with dr/dc, guard bounds; (2) graph → adjacency-list dict (both directions for undirected); (3) shortest steps → BFS with a deque (FIFO); (4) reachability / region size → recursive DFS or flood-fill with a visited set passed as an argument; (5) always skip visited nodes to avoid cycles.

Recap

The offsets (-1,0), (1,0), (0,-1), (0,1) reach a cell's neighbours; guard with 0 <= nr and nr < rows.
An undirected edge is added to BOTH endpoints' lists, and len(adj[node]) is the degree.
Flood-fill and DFS recurse into unvisited neighbours, with the visited set passed as an argument.
BFS uses a deque queue (append, popleft), so the first arrival at a cell is by a shortest path.
After a DFS from the start, target in visited tells whether the target is reachable.

You can now traverse grids and graphs to answer region, distance and reachability questions.