PYTHON 3 · CCC JUNIOR · LESSON 8 · PRACTICE

Six Past CCC Problems, One Engine 🔁

Every problem below runs on the Lesson 8 machinery: define the state, choose → explore → undo, and know exactly what visited means.

Work the logic first. The animations walk the official samples — try to predict each step before you press Step.

★ The Recursion Recipe — use it on every problem below: 1 · BASE CASE the smallest state, answered directly   2 · MAKE IT SMALLER every call moves one step closer to it   3 · CALL ITSELF + COMBINE trust the smaller answer and return what you build from it — or, for search problems, CHOOSE → EXPLORE → UNDO. Before coding, say out loud: what is my state, what is my smallest state, and how does it shrink?
START HERE · BEFORE THE CCC PROBLEMS

★ Start Simple — Five Tiny Questions, One Per Page

The CCC problems below have long stories. These five do not — short words, small numbers, same Recipe. Each one now has its own page (use the Next button or the chips above): the question, a step-by-step walkthrough with the code and the call tree moving together, the code, and a predict-first check. Do them in order — the first four are chains (each call has exactly one child), and the fifth is your first real tree.

1 · Factorial — multiply on the way up

factorial(5) → 120. The chain in its purest form: calls pile up, answers multiply back.

2 · Bunny Ears — add the same thing

bunny_ears(3) → 6. Same chain, gentler combine step: + 2 per bunny.

3 · Triangle — rows of blocks

triangle(4) → 10. Each call adds its own row and trusts the smaller triangle for the rest.

4 · Count the x's — a string that shrinks

count_x("xxhixx") → 4. The state is a string; the smaller problem drops its first letter.

5 · Fibonacci — your first tree 🌳

fib(6) → 8. Two calls per call — the chain becomes a tree, and you can count the waste yourself.

Done with these five? Then the CCC problems below are the same Recipe with longer stories. When a story feels heavy, find these three things in it first: the state, the base case, and how it shrinks — the rest is combining.
TINY QUESTION 1 OF 5 · A CHAIN

Factorial — multiply on the way up

factorial(n) means n × (n−1) × … × 1.

factorial(5) → 120

BASE factorial(0) = 1
SMALLER factorial(n − 1)
COMBINE n × that answer

The code

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 120
✏️ Predict: factorial(4)?

24 — 4 × factorial(3) = 4 × 6.

TINY QUESTION 2 OF 5 · A CHAIN

Bunny Ears — add the same thing

Every bunny has 2 ears. How many ears on b bunnies — counted one bunny at a time?

bunny_ears(3) → 6

BASE bunny_ears(0) = 0
SMALLER one fewer bunny
COMBINE 2 + that answer

The code

def bunny_ears(b):
    if b == 0:
        return 0
    return 2 + bunny_ears(b - 1)

print(bunny_ears(3))   # 6
✏️ Predict: bunny_ears(10)?

20 — ten bunnies, two ears each, built two at a time.

TINY QUESTION 3 OF 5 · A CHAIN

Triangle — rows of blocks

Row 1 has 1 block, row 2 has 2, row 3 has 3… How many blocks in a triangle of r rows?

triangle(4) → 10

BASE triangle(0) = 0
SMALLER one fewer row
COMBINE r + that answer

The code

def triangle(r):
    if r == 0:
        return 0
    return r + triangle(r - 1)

print(triangle(4))   # 10
✏️ Predict: triangle(5)?

15 — 5 + triangle(4) = 5 + 10.

TINY QUESTION 4 OF 5 · A CHAIN

Count the x's — a string that shrinks

Count the letter x in a string. The “smaller problem” is the string with its first letter removed.

count_x("xxhixx") → 4

BASE empty string → 0
SMALLER s[1:] — drop the first letter
COMBINE (1 if the first letter is x) + the rest

The code

def count_x(s):
    if s == "":
        return 0
    first = 1 if s[0] == "x" else 0
    return first + count_x(s[1:])

print(count_x("xxhixx"))   # 4
✏️ Predict: count_x("xhix")?

2 — an x at the start and an x at the end.

TINY QUESTION 5 OF 5 · YOUR FIRST TREE 🌳

Fibonacci — your first tree

Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… This one branches — it is the routes tree from §2 with different base cases.

fib(6) → 8

BASE fib(0) = 0 · fib(1) = 1
SMALLER fib(n − 1) and fib(n − 2)
COMBINE add the two answers

The code

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(6))   # 8
✏️ Predict: fib(7)?

13 — fib(6) + fib(5) = 8 + 5. Draw its tree the §2 way and count how many times fib(2) gets built!

CCC 2023 · JUNIOR J5 · CORE PRACTICE

CCC Word Hunt 🔤

Connection to the lesson: §3 + §5 — explore starting cells and directions with recursive state. The bend is just a state change mid-word: after the turn, the direction component of the state is different.
❓ THE QUESTION

How many times is the word hidden in the letter grid?

Input: the word W (distinct uppercase letters), then R and C, then the grid — letters separated by spaces. The word may lie on one straight segment (horizontal, vertical, or diagonal, in either direction) or on two perpendicular segments — bending once, at a right angle, at any letter after the first.

Sample input

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

Sample output

3

Output: one integer — the number of occurrences.

How to think about it: Do not write 8 directions × bend positions as one giant tangle. Write one helper — seg_ok — that checks whether a piece of the word can be read from a cell in a direction. Then a straight occurrence is one call, and a bent occurrence is two calls with perpendicular directions (their dot product is 0).
How to read this walkthrough — three views, moving together. Left: the code, with the line running right now lit up. Below: the grid. Middle: an attempt tree — Word Hunt's printed solution is loops, not recursion, so instead of a call tree you get one box per try from a single start cell: directions, bends, and legs, each marked with exactly why it lived or died. Step through and watch the three views agree.

The code

import sys

def main():
    lines = sys.stdin.read().split("\n")
    W = lines[0].strip()
    R = int(lines[1])
    C = int(lines[2])
    grid = [lines[3 + r].split() for r in range(R)]
    L = len(W)
    DIRS = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
            (0, 1), (1, -1), (1, 0), (1, 1)]

    def seg_ok(r, c, dr, dc, i0, i1):
        # can W[i0:i1] be read starting at (r, c), stepping (dr, dc)?
        for i in range(i0, i1):
            rr = r + dr * (i - i0)
            cc = c + dc * (i - i0)
            if not (0 <= rr < R and 0 <= cc < C):
                return False
            if grid[rr][cc] != W[i]:
                return False
        return True

    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != W[0]:
                continue
            for dr, dc in DIRS:
                if seg_ok(r, c, dr, dc, 0, L):
                    count += 1                      # straight
                for k in range(1, L - 1):           # bend after letter k
                    br, bc = r + dr * k, c + dc * k
                    if not seg_ok(r, c, dr, dc, 0, k + 1):
                        break
                    for dr2, dc2 in DIRS:
                        if dr * dr2 + dc * dc2 != 0:
                            continue                # second leg must be perpendicular
                        if seg_ok(br, bc, dr2, dc2, k, L):
                            count += 1
    print(count)

main()

Key points & traps

The bend needs at least one letter on each side. The bend index k ranges over 1…L−2 (0-based split after letter k): bending “before the first letter” or “after the last” is just a straight word counted twice.
Perpendicular, not just “different”. For direction vectors, perpendicular ⟺ dot product = 0. That one test replaces pages of casework — and it also excludes continuing straight and reversing.
Cells are reusable across different occurrences — there is no visited grid here at all. Each candidate placement is checked independently.
Why not DFS letter by letter? You could — the state would be (cell, index, direction, bent?). The segment helper is the same search with the straight-line parts pre-verified. Both are correct; the helper has fewer places to hide an off-by-one.
✏️ Predict first: word CAT, grid below — how many occurrences? (Count the bend!)
C A .
. T .
. . .

Answer: 1. C(0,0) → A(0,1) heading east, then bend south (perpendicular) to T(1,1). No straight placement exists: the T is not in line with C and A in any single direction. If you answered 0, your search is missing bent words — the 9-mark part of the problem.

CCC 2015 · JUNIOR J5 · CORE COUNTING

π Day 🥧

Connection to the lesson: §2 + §4 — recursively distribute pieces in non-decreasing order. The minimum parameter is the trick that kills duplicates, and memoization on the full state (left, people, minimum) makes n = 250 survivable.
❓ THE QUESTION

In how many ways can n pieces of pie be given to k people in line, if everyone gets at least one piece and nobody gets fewer than the person in front of them?

Input: n (pieces, up to 250), then k (people). Amounts must be non-decreasing along the line.

Sample input

8
4

Sample output

5

Output: one integer — the number of distributions.

How to think about it: Decide the amounts person by person. The state needs three numbers: pieces left, people remaining, and the minimum the next person may take (= what the previous person took). The next amount can range from minimum up to left // people — beyond that, the people behind cannot all keep up. The official example lists the five ways for 8/4: [1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2].
How to read this walkthrough — three views, moving together. Left: the code, with the line running right now lit up. Middle: the call tree — one box per call: solid blue is running now, pale blue is a caller waiting, green is finished (with what it returned), red dashed is a branch that was abandoned. Below: the state. Step through and watch the three views agree.

The code

from functools import lru_cache

n = int(input())
k = int(input())

@lru_cache(None)
def ways(left, people, minimum):
    # ways to give `left` pieces to `people` people so that each
    # person gets at least `minimum` and amounts never decrease
    if people == 1:
        return 1                      # last person takes everything left
    total = 0
    for first in range(minimum, left // people + 1):
        total += ways(left - first, people - 1, first)
    return total

print(ways(n, k, 1))

Key points & traps

The minimum parameter IS the non-decreasing rule. Without it you would count [1, 2] and [2, 1] as different distributions and need a second pass to remove duplicates. Build the rule into the state instead.
Base case people == 1 → 1. The last person takes everything left; there is no choice left to make. (If left < people × minimum the loop simply runs zero times and returns 0 — impossible branches price themselves out.)
Memoize the full state. The answer depends on all three numbers, so the cache key is all three. Drop minimum from the state and the cache returns wrong answers — the §2 test again: cache only when the full state determines the answer.
Special cases agree: k = 1 → 1 way (one person takes all); k = n → 1 way (everyone gets exactly 1). Check your code against both before submitting.
✏️ Predict first: 5 pieces, 2 people — how many ways?

Answer: 2 — [1, 4] and [2, 3]. ([3, 2] and [4, 1] break the non-decreasing rule.)

CCC 2019 · JUNIOR J5 · BACKTRACKING CHALLENGE

Rule of Three 🔀

Connection to the lesson: §3 in its purest form — choose a rule and a position, explore, and on failure pop the recorded step and try the next choice. The answer is not a count; it is the recorded path itself.
❓ THE QUESTION

A word-rewriting game: use exactly S moves to turn the START string into the TARGET string — then print the diary of the moves you used.

Input is four lines. The first three lines are the three rewriting rules, each written pattern replacement (strings of A's and B's). The fourth line holds three things at once — S I F: S = the exact number of moves you must make, I = the initial (start) string, F = the final (target) string. One move replaces one occurrence of a rule's pattern, at a position you choose. A solution is guaranteed to exist. If this still sounds tangled, the green Decode box right below this card walks the sample input and output line by line.

Sample input

AA AB
AB BB
B AA
4 AB AAAB

Sample output

2 1 BB
3 1 AAB
3 3 AAAA
1 3 AAAB

Output: S lines, each rule position resulting-string (positions are 1-based). Any valid sequence is accepted.

How to think about it: Search depth-first over (rule, position) choices, keeping the list of steps taken. The base case is steps_used == S: succeed only if the string is exactly F, otherwise this branch is dead — pop and move on. The animation follows the actual search, including its one dead end.

🔍 Decode the question — what is it actually asking?

In plain words: you are given a short string of A's and B's, like AB. You are also given three find-and-replace rules. One move = pick a rule, find its left-hand pattern somewhere in your current string, and replace that one occurrence with the rule's right-hand side. You must make exactly S moves — not “up to S” — and after the last move your string must be exactly the target. The question is not asking whether it can be done (it promises it can). It is asking you to find one winning sequence of moves — and print it.

📥 The INPUT, line by line (sample)

LineSampleWhat it means
1AA ABRule 1: wherever you find AA, you may replace it with AB
2AB BBRule 2: wherever you find AB, you may replace it with BB
3B AARule 3: wherever you find B, you may replace it with AA
44 AB AAABThree values in one line: 4 = S, make exactly 4 moves · AB = I, the start string · AAAB = F, the target string

📤 The OUTPUT — it is a diary of your moves, not the final string

Print S lines (here, 4 lines) — one line per move. Every line has three parts: the rule number you used, the position where its pattern starts in the current string (1-based — the first character is position 1), and the whole string after that move. Here is the sample output, decoded move by move:

BeforeOutput lineRead it as…After
AB2 1 BBRule 2 at position 1: AB → BBBB
BB3 1 AABRule 3 at position 1: the first B → AA; the second B staysAAB
AAB3 3 AAAARule 3 at position 3: that B → AAAAAA
AAAA1 3 AAABRule 1 at position 3: the AA starting there → AB; the first AA is untouchedAAAB 🎯

After exactly 4 moves the string is AAAB — the target — so this diary wins. Any diary that reaches the target in exactly S moves is accepted: the animation and the code below find a different valid diary for this same input, and that is fine. Recipe check for this problem — base case: used == S and the string equals F; make it smaller: one move spent, S − used shrinks by 1 each call; self-call: choose a (rule, position), explore it, and on failure pop the recorded step and try the next choice.

How to read this walkthrough — three views, moving together. Left: the code, with the line running right now lit up. Middle: the call tree — one box per call: solid blue is running now, pale blue is a caller waiting, green is finished (with what it returned), red dashed is a branch that was abandoned. Below: the state. Step through and watch the three views agree.

The code

import sys
sys.setrecursionlimit(10000)

rules = []
for _ in range(3):
    a, b = input().split()
    rules.append((a, b))
S, I, F = input().split()
S = int(S)

steps = []          # the record: (rule number, position, resulting string)

def dfs(cur, used):
    if used == S:
        return cur == F
    for ri in range(3):
        a, b = rules[ri]
        start = 0
        while True:
            p = cur.find(a, start)
            if p == -1:
                break
            nxt = cur[:p] + b + cur[p + len(a):]
            steps.append((ri + 1, p + 1, nxt))     # record the choice
            if dfs(nxt, used + 1):
                return True
            steps.pop()                            # undo - try the next choice
            start = p + 1
    return False

dfs(I, 0)
for ri, p, w in steps:
    print(ri, p, w)

Key points & traps

The record list is the answer. Append on the way down, pop on the way back — when the search finally succeeds, the list holds exactly the winning sequence. Forgetting the pop leaves dead steps in the output.
Exactly S steps — not at most S. Reaching F early is not success unless used == S. The base case checks both conditions together.
Positions are 1-based in the output but 0-based in str.find. The +1 when recording is the easiest mark to lose in this problem.
Overlapping matches count. After a failed position, continue searching from p + 1, not from p + len(pattern) — patterns like AA inside AAA occur twice.
✏️ Predict first: in the official sample solution, after 2 1 BB and 3 1 AAB, rule 3 is played at position 3. What string results?

AAAA. AAB's B is at position 3; rule 3 (B→AA) replaces it: AA + AA = AAAA. One more step (rule 1 at position 3) turns AAAA into the target AAAB.

CCC 2004 · JUNIOR J5 · OPTIONAL VISUAL CHALLENGE

Fractals 🌀

Connection to the lesson: §1 + §6 — recursive decomposition with a geometric state: a segment is (start, direction, bump side, length), and a level-L segment is exactly five level-(L−1) segments. The base level just draws.
❓ THE QUESTION

Where does a vertical line cross the block fractal?

Every segment is split into thirds; the middle third becomes a square bump. Given a level, a width (a power of 3, at most 81), and an x-coordinate, output every y where the fractal's lines pass through the point (x, y), in increasing order. The fractal starts as the segment from (0, 1) to (width, 1).

Sample inputs

3 27 5
3 27 18
2 27 19
4 81 38

Sample outputs

4 5 6
1 2 3 4 7 8 9 10
1 4 7
37 38 39
How to think about it: do not try to “draw then scan”. Recurse on segments: at level 0 a segment contributes its integer points; above level 0 it contributes the points of its five children — two straight, and the bump's up-across-down, whose directions are the parent's direction rotated. Collect points in a set, then answer the query. Play with the picture first:
query x = 38 · level 4 · y values at this x:

See the code section below for the full program — and try the slider: at level 4 with x = 38 the picture reports exactly the fourth sample's answer, 37 38 39.

New: this problem gets a walkthrough too — three views, moving together. Left: the split() code, with the line running right now lit up. Middle: the call tree — one box per call: solid blue is running now, pale blue is a caller waiting, green is finished; finished branches fold up so the frontier stays visible. Below: the drawing itself, growing segment by segment in exactly the order the leaf calls draw them. It traces level 2, width 9 — the same code the playground above runs at bigger sizes.

The code

level, width, xq = map(int, input().split())
points = set()

def split(x, y, dx, dy, nx, ny, length, lev):
    # one segment: start (x, y), direction (dx, dy), bump side (nx, ny)
    if lev == 0:
        for i in range(length + 1):
            points.add((x + dx * i, y + dy * i))
        return
    t = length // 3
    x1, y1 = x + dx * t, y + dy * t            # end of first third
    x2, y2 = x1 + nx * t, y1 + ny * t          # up the bump
    x3, y3 = x2 + dx * t, y2 + dy * t          # across the top
    x4, y4 = x3 - nx * t, y3 - ny * t          # down to the last third
    split(x,  y,  dx,  dy,  nx,  ny,  t, lev - 1)
    split(x1, y1, nx,  ny,  -dx, -dy, t, lev - 1)
    split(x2, y2, dx,  dy,  nx,  ny,  t, lev - 1)
    split(x3, y3, -nx, -ny, dx,  dy,  t, lev - 1)
    split(x4, y4, dx,  dy,  nx,  ny,  t, lev - 1)

split(0, 1, 1, 0, 0, 1, width, level)
ys = sorted(y for (px, y) in points if px == xq)
print(*ys)

Key points & traps

Four orientations. A segment's bump can point up, down, left, or right. Carrying the direction (dx, dy) and the bump-side normal (nx, ny) through the recursion handles all four with one code path — the bump children use rotated pairs.
Shared corners are fine. Neighbouring segments share endpoints; a set of points absorbs the duplicates for free.
Width is a power of 3 so every third is a whole number of unit steps — level L has segment length width / 3L ≥ 1, guaranteed by the problem.
Recursion depth is tiny (level ≤ 4 for width 81) but the point count explodes: 5L segments. Decompose, don't simulate pixel by pixel.
✏️ Predict first: level 1, width 27, x = 13 — which y values?

Answer: 10. At level 1 the bump occupies the middle third (x from 9 to 18) and rises 9 units above y = 1, so its top edge is the segment y = 10 — and x = 13 crosses only that top edge.

CCC 2024 · JUNIOR J5 · JUNIOR→SENIOR BRIDGE

Harvest Waterloo 🎃

Connection to the lesson: §5's mirror image — flood fill through reachable cells, accumulating values. The distinction Rui's table flags: visited is permanent here; there is no undo, because a cell only ever needs processing once.
❓ THE QUESTION

What is the total value of every pumpkin the farmer can reach?

The patch is rows of S (small, $1), M (medium, $5), L (large, $10) and * (hay). The farmer starts at row A, column B and moves up/down/left/right — never through hay, never outside. Harvest everything reachable.

Sample input

6
6
**LMLS
S*LMMS
S*SMSM
******
LLM*MS
SSL*SS
5
1

Sample output

37

Output: one integer — the total value.

How to think about it: One flood fill from the start cell: on first arrival at a cell, add its value and spread to its four neighbours. The hay row across the middle splits the patch — the top region, however rich, is simply not in the farmer's connected component.
How to read this walkthrough — three views, moving together. Left: the code, with the line running right now lit up. Middle: the call tree — one box per call: solid blue is running now, pale blue is a caller waiting, green is finished (with what it returned), red dashed is a branch that was abandoned. Below: the state. Step through and watch the three views agree.

The code

import sys
sys.setrecursionlimit(1000000)

R = int(input())
C = int(input())
grid = [input().strip() for _ in range(R)]
A = int(input())
B = int(input())

VALUE = {'S': 1, 'M': 5, 'L': 10}
visited = [[False] * C for _ in range(R)]

def fill(r, c):
    if not (0 <= r < R and 0 <= c < C):
        return 0
    if visited[r][c] or grid[r][c] == '*':
        return 0
    visited[r][c] = True            # permanent: never unmarked
    total = VALUE[grid[r][c]]
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        total += fill(r + dr, c + dc)
    return total

print(fill(A, B))

Key points & traps

Mark on arrival, never unmark. Compare §5 line by line: the only structural difference is the missing visited[r][c] = False. That one line is the difference between “count every path” and “visit every cell once” — and it changes the running time from exponential to O(R × C).
Add each value exactly once — at the moment of first marking. Add on arrival, not on “leaving”, or shared neighbours will double-count.
Depth warning: on the largest patches a recursive fill can exceed Python's recursion limit. The identical algorithm with an explicit stack (a list used with append/pop) or a BFS queue has no depth problem — same marking rule, different engine.
The start cell is given as (A, B) = (row, column) on separate lines at the end — read all the numbers in order and don't swap them.
✏️ Predict first: patch below, farmer starts at (1, 0). Total value?
S S
M *

Answer: 7. From (1, 0) the M ($5) is harvested, then up to (0, 0) S ($1) and right to (0, 1) S ($1). The hay at (1, 1) blocks nothing else — everything reachable totals 5 + 1 + 1 = 7.

CCC 2020 · JUNIOR J5 / SENIOR S2 · BRIDGE EXTENSION

Escape Room 🚪

Connection to the lesson: §5's reachability idea grown up: the “neighbours” of a cell are computed (factor pairs of its value), the graph can have a million cells, and — per Rui's table — the search should be iterative (queue/stack), with each distinct value expanded only once.
❓ THE QUESTION

Can you escape from the top-left cell to the bottom-right cell?

An M×N room; every cell holds a positive integer. Standing on a cell with value x, you may jump to any cell (a, b) with a × b = x (rows and columns are 1-based). Start at (1, 1); the exit is (M, N).

Sample input

3
4
3 10 8 14
1 11 12 12
6 2 3 9

Sample output

yes

Output: yes or no.

How to think about it: This is a graph problem wearing a grid costume. The vertices are cells; the edges come from factoring. Explore with a queue (BFS) or stack (DFS) — for reachability the order does not matter, but two efficiency rules do: mark cells when they are added, and expand each distinct value at most once, because every cell holding x has exactly the same jumps.
How to read this walkthrough — three views, moving together. Left: the code, with the line running right now lit up. Below: the room and the queue. Middle: the BFS tree — Escape Room's printed solution is a queue, not recursion, so each box is a reached cell and its parent is the cell that discovered it: solid blue is being expanded now, pale blue is waiting in the queue, green is fully expanded. Step through and watch the three views agree.

The code

from collections import deque

M = int(input())
N = int(input())
grid = []
for _ in range(M):
    grid.append(list(map(int, input().split())))

seen_cell = [[False] * N for _ in range(M)]
seen_value = set()
queue = deque()
queue.append((0, 0))
seen_cell[0][0] = True

while queue:
    r, c = queue.popleft()
    if (r, c) == (M - 1, N - 1):
        break
    x = grid[r][c]
    if x in seen_value:
        continue                    # this value's jumps were already explored
    seen_value.add(x)
    a = 1
    while a * a <= x:               # factor pairs of x
        if x % a == 0:
            b = x // a
            for rr, cc in [(a - 1, b - 1), (b - 1, a - 1)]:
                if 0 <= rr < M and 0 <= cc < N and not seen_cell[rr][cc]:
                    seen_cell[rr][cc] = True
                    queue.append((rr, cc))
        a += 1

print("yes" if seen_cell[M - 1][N - 1] else "no")

Key points & traps

Factor pairs are the neighbour generator. For value x, try a from 1 to √x; each divisor gives two target cells, (a, b) and (b, a) — then keep only the ones inside the room. Never scan the whole room per cell: that is 1012 work at full size.
seen_value is the Senior touch. A value like 12 can appear in thousands of cells; its jump targets never change. Expanding it once turns a hopeless search into a fast one.
Iterative, on purpose. With up to 106 cells, a recursive DFS can nest a million deep. A deque (BFS) or a list stack (DFS) keeps the “call stack” in ordinary memory.
1-based coordinates. The jump rule uses (row, column) starting at 1 — that is why the code subtracts 1 when converting a factor pair into list indexes. Off-by-one here flips yes to no.
✏️ Predict first: room below — yes or no?
2
2
2 3
5 7

Answer: no. From (1, 1) = 2 you can jump to (1, 2) and (2, 1). Their values, 3 and 5, only point outside the 2×2 room (3 = 1×3, 5 = 1×5). The exit (2, 2) needs a jump from a cell holding 4 — there is none.

Where to go next: revisit any problem whose animation surprised you, then close the page and write its code from the logic plan alone. That — not re-reading — is what makes the pattern yours. Exam soon? The concept page's §6 routine is the checklist to run on any new search problem.