Graph Search, State Space, And Path Optimization

What's being tested

These problems test graph traversal, state-space modeling, and path optimization under constraints. You need to choose between DFS + memoization, BFS over encoded states, and DAG dynamic programming, then justify correctness, reconstruction, and O(V + E)-style complexity.

Patterns & templates

• DFS + memoization for longest decreasing grid paths — dfs(r,c) returns best suffix; O(R*C) states, avoid revisiting recomputation.

• Topological DP on DAGs — process nodes in topo order; update dp[v] = max(dp[v], dp[u] + reward - cost).

• BFS over state space — encode (row, col, keysMask) for shortest key collection; first time reaching full mask is optimal.

• Bitmask state encoding — map keys to bits using 1 << k; visited becomes visited[r][c][mask], often O(R*C*2^K).

• Path reconstruction — store parent[state] = prevState or next[node]; reconstruct after DP/BFS without polluting scoring logic.

• Grid graph idiom — use dirs = [(1,0),(-1,0),(0,1),(0,-1)]; bounds-check before height, wall, lock, or visited checks.

• Score vs distance distinction — BFS minimizes unweighted steps; weighted DAG maximization needs DP, not greedy local best or plain BFS.

Common pitfalls

Pitfall: Treating (r, c) as visited in key-collection problems is wrong; the same cell with different keys is a different state.

Pitfall: Using DFS without memoization on decreasing-path grids can explode exponentially despite the grid having only R*C meaningful states.

Pitfall: Forgetting to prove acyclicity before DAG DP; if cycles exist, longest/max-score path may be undefined or require different algorithms.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.