Unique Paths III
Hard · Backtracking · about 30 minutes
Asked at Google, Amazon, Meta, Microsoft.
grid marks the start with 1, the finish with 2, open cells with 0 and blocked cells with -1. Count the routes that go from start to finish, moving between side-adjacent cells, and step on every unblocked cell exactly once.