Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Blocked Matrix.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Unique paths with obstacles matches the clues
- 2Keep this true after every move: after processing a cell, dp[col] counts valid paths to it without crossing an obstacle
- 3Reach the result within O(rows times cols) time and O(cols) space
Rules and pressure
- Target cost: O(rows times cols) time and O(cols) space
- State rule: after processing a cell, dp[col] counts valid paths to it without crossing an obstacle
Lesson 1 of 3
Live algorithm trace
Unique paths with obstacles
Complete execution1 of 6
0
cell
0
0
0
1
0
0
0
0
Seed the open start cell with one path.
1
dp[0] = 12
scan cells row by row3
if obstacle: dp[col] = 04
else if col > 05
dp[col] += dp[col - 1]6
return dp[last]dp = [1,0,0]
Truth to preserve / Cost target
Truth to preserve
after processing a cell, dp[col] counts valid paths to it without crossing an obstacle
Cost target
O(rows times cols) time and O(cols) space
A blocked cell contributes zero paths. Every open cell still combines its reachable arrivals from above and left.
Your call · What should guide every step of this algorithm?