Skip to content
CCC Python Course

State-space graph modelling and sparsification

Stage
6
Module
M6.2
Lessons
1

In this module

  • Model a problem as a shortest-path search by representing states as nodes.
  • Identify which edges matter in practice, even when the full state graph is enormous.
  • Implement reachability search with pruning and edge filtering.
  • Measure the sparsified graph's size and confirm it solves the problem.

Before this module

M6.1Dijkstra's shortest pathsM4.2Sorting with keys, and greedy

Lessons

  1. 1State-space graph modelling and sparsification

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2025 S4
    Floor is Lava (opens on WMOJ in a new tab) WMOJ

    Expand each state to include a resource level, then search the larger graph for a shortest path.

  2. 2018 S3
    RoboThieves (opens on DMOJ in a new tab) DMOJ

    Collect objects by moving through a grid, avoiding certain states.

    Why DMOJ: An older problem whose forced moves are naturally modelled as an expanded state space.