Skip to content

Broken Profile Hot Sheet

Use this page when one grid dimension is small and the real state is the frontier between processed and unprocessed cells.

Do Not Use When

  • the mask is really a subset of items instead of a grid frontier
  • both grid dimensions are large enough that 2^min(n, m) is already dead
  • the frontier must store connectivity labels and the simple occupancy starter is no longer enough

Choose By Signal

  • domino tiling or local-fill DP on a small-width grid -> broken-profile-domino-tiling.cpp
  • same family, but frontier must remember pairings / connectivity -> reopen the full topic page before coding
  • subset of items / tasks / vertices -> Bitmask DP

Core Invariants

  • rotate so the smaller dimension becomes the masked frontier
  • mask means which cells of the current column are already occupied before filling it
  • row DFS builds one next_mask
  • vertical placement stays inside the current column
  • horizontal placement writes a bit into next_mask

Main Traps

  • mixing current-column occupancy with next-column occupancy
  • not fixing one consistent meaning for bit 1
  • trying to jump straight to plug DP with connectivity labels
  • forgetting odd-area boards have zero domino tilings

Exact Starter Route

Reopen Paths