Every Route Through the Garden
garden is a list of equal-length strings that form a grid: . is a path cell and # is a hedge. A route starts in the top-left cell, ends in the bottom-right cell, moves one cell up, down, left or right at a time, never enters a hedge, never leaves the grid, and never visits a cell twice. Return the number of different routes. If the top-left or the bottom-right cell is a hedge there are no routes, and a garden whose only cell is a path cell has exactly one route, which does not move at all.
The grid is small, so backtracking is the intended approach: step onto a neighbour, mark it as visited, count the routes from there, then unmark it before trying the next neighbour.
For example, ["...", "...", "..."] has 12 routes, and ["...", ".#.", "..."] has 2.
Example 1
In a 3 by 3 garden with no hedges there are 12 routes from corner to corner that never revisit a cell.
Example 2
With the centre blocked, a route must go round it along the top and right edges or along the left and bottom edges.
Constraints
1 <= len(garden) <= 5and1 <= len(garden[i]) <= 5- Every row has the same length
- Every cell is
.or#
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Fair SplitMedium
- Fill In the BracketsMedium
- Hidden Word CountMedium
- Maze EscapeMedium
- Numbers RoundMedium
- Tower MovesMedium
- Tower With a Middle StopMedium
- Where the Trace Can StartMedium