Standard Bar Dynamic Programming · 2D DP O(m*n) · O(n)
The courier's follow-up run happens during a stocktake, and some grid blocks are sealed by pallet stacks. The drone still flies only east and south from the northwest depot to the southeast customer, but no flight plan may cross a sealed block. Dispatch needs the count of valid routes that skirt every obstacle so it can promise realistic delivery options.
Input: An m x n matrix grid where 0 marks an open block and 1 marks an obstacle.
Output: Return the number of obstacle-free down/right paths from the top-left to the bottom-right cell.
1 <= m, n <= 100grid[i][j] is 0 or 1the answer fits in a 32-bit signed integerInput: {"grid":[[0,0,0],[0,1,0],[0,0,0]]}
Output: 2
Only the hugging-the-edge routes survive: all-right-then-down and all-down-then-right.
Input: {"grid":[[0,1],[0,0]]}
Output: 1
The blocked corner forces the single route: down, then right.