Statementâ–¼
You are given a  grid
, where each cell, grid[i][j]
, can have one of the following values:
1
indicates the starting point. There is exactly one such square.2
marks the ending point. There is exactly one such square.0
represents empty squares that can be walked over.-1
represents obstacles that cannot be crossed.
Your task is to return the total number of unique four-directional paths from the starting square (1
) to the ending square (2
), such that every empty square is visited exactly once during the walk.
Constraints:
m == grid.length
n == grid[i].length
1≤ m,n ≤20 1≤ m×n ≤20 −1≤ grid[i][j]
≤2 There is exactly one starting cell and one ending cell.
Solution
The main goal is to find every possible path that visits each empty square exactly once, without stepping on obstacles or revisiting any cell. This can be done using backtracking, which explores different paths and steps back when a dead end is reached. The first step is identifying the starting square and counting the total number of walkable squares in the grid. Walkable squares include all empty cells (0
), the starting square (1
), and the ending square (2
).
Once the number of walkable squares is determined, the algorithm begins a recursive exploration of all valid paths starting from the starting square. It marks the current square as visited and decreases the count of remaining walkable squares to be visited. This prevents revisiting the same square in the current path. The algorithm then tries to move in one of the four possible directions (up, down, left, and right) while staying within the grid boundaries and avoiding any visited or blocked cells. This leads to two possible outcomes:
When a new valid square is reached, the process repeats: the new square is marked as visited, and its neighbors are explored recursively, i.e., one of the possible directions is tried.
The tried direction doesn't lead to a valid path, i.e., the algorithm can't reach any walkable cell. When this happens, the algorithm backtracks in two ways:
If there are still unexplored directions from the current square, it restores the current square to its original (unvisited) state so it can be used again in other potential paths. It then tries another direction, for example, if it previously moved upward, it might now try moving downward, right, or left.
If all directions from the current square have already been tried and none lead to a valid path, the algorithm backtracks to the previous square and continues exploring any remaining unexplored directions from there.
The base case of this recursive exploration is reached when only one walkable square remains, and that square is the ending square (i.e., its value is 2
). At that moment, the path is counted as valid.
After a valid path is found, the algorithm does not explore further from the ending square, but it still automatically backtracks to the previous square when the recursion unwinds. This is important because other unexplored directions may be earlier in the path that could lead to different valid routes. Eventually, this ensures that all possible valid paths are discovered and counted.
Let's look at the algorithm steps:
Initialize variables:
Set
total_walkable_squares
to 0 to count all non-obstacle squares (including start and end).Set
start_x
andstart_y
to 0 as placeholders for the starting square’s position.
Traverse each cell in the
grid
. For each cell in the grid:If the cell is not an obstacle (
0
,1
, or2
), increasetotal_walkable_squares
by 1.If the cell is the starting point (
1
), updatestart_x
andstart_y
to its coordinates.
Start exploring the valid paths from the starting square by calling the recursive function
explorePaths()
with the currentgrid
,start_x
,start_y
, andtotal_walkable_squares
. TheexplorePaths()
function works as follows:For the base case, if the current square is the ending square (
2
) and only one square is left to visit (remaining_walkable_squares == 1
), return 1 to count this as a valid path.Mark the current square as visited by temporarily storing its value and setting it to a marker,
-4
. This in-place marking helps avoid using extra space for tracking visited cells. Decreaseremaining_walkable_squares
by 1 as this square is now considered visited.Once the cell is marked visited, explore all four directions. For each direction (up, down, left, right):
Compute the new position.
If the new position is inside the grid and not an obstacle or already visited, recursively call
explorePaths()
for the new position with the updatedremaining_walkable_squares
value. Add the result to the total path count.
Backtrack, i.e., restore the cell to its original value so it can be used again in a different path.
Return the total number of valid paths from this point.
Return the final result from the initial call.
The slides below help to understand the solution in a better way.