Solution
Approach 1: Backtracking DFS
Intuition and Algorithm
Let's try walking to each 0
, leaving an obstacle behind from where we walked. After, we can remove the obstacle.
Given the input limits, this can work because bad paths tend to get stuck quickly and run out of free squares.
Complexity Analysis

Time Complexity: , where are the number of rows and columns in the grid. (We can find tighter bounds, but such a bound is beyond the scope of this article.)

Space Complexity: .
Approach 2: Dynamic Programming
Intuition and Algorithm
Let dp(r, c, todo)
be the number of paths starting from where we are (r, c
), and given that todo
is the set of empty squares we've yet to walk on.
We can use a similar approach to Approach 1, except we will memoize these states (r, c, todo)
so as not to repeat work.
Complexity Analysis

Time Complexity: , where are the number of rows and columns in the grid.

Space Complexity: .
Analysis written by: @awice.