FunctionRacerProblemsRace

Every Route Through the Garden

MediumRecursionPython, JavaScript, TypeScript, Java, C++

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

garden ["...","...","..."]
returns 12

In a 3 by 3 garden with no hedges there are 12 routes from corner to corner that never revisit a cell.

Example 2

garden ["...",".#.","..."]
returns 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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems