Since upward moves are forbidden, once a path leaves a row for the next row, it never returns. Reversing its horizontal direction within a row would immediately revisit the preceding cell. Thus, all horizontal moves within one row must have the same direction.
Remembering only the last direction is insufficient. When the last move was down, the direction before it determines which horizontal move is allowed next. Use the following five states:
Also treat the starting cell, before any move, as state . A downward first move likewise leads to state .
Let be the maximum distance of a valid path reaching cell in state . Use for unreachable states. Initially, , and every other state is unreachable. States at walls and outside the grid are also unreachable. Never create a new path by adding to an unreachable value.
First consider moves down from the cell above. After a horizontal move, remember its direction for one more step. After another downward move, this restriction on the horizontal direction disappears:
Apply these equations to passable cells with , keeping the starting cell's initial value.
A move right may follow only states , , and . Reversing direction from would revisit a cell, while moving right from would form a forbidden sequence of three moves. Hence,
Symmetrically, a move left is given by
For each row, compute all three states for downward arrivals first. Then scan from left to right to compute the states, and from right to left to compute the states. There are no transitions between the two horizontal states, so this order evaluates every recurrence correctly. Initialize all states of each new row as unreachable, and never update a state at a wall.
Output the maximum of the five states at the destination. If all are unreachable, output . The states already store distances, so no conversion from the number of visited cells is needed.
There are only a constant number of states per cell, giving a time complexity of . Keeping only the preceding and current rows of states and reading the grid one row at a time gives a space complexity of .
Proof
A valid path never moves up, so it enters each row at most once. If it moves in both horizontal directions within a row, its first reversal immediately returns to the preceding cell. Therefore, horizontal moves within a row have only one direction. Moving down enters an unvisited row, and continuing in one horizontal direction enters an unvisited cell. The recurrences never transition from the opposite horizontal state in the same row, so they cannot cause a repeated visit.
Before a move right, exactly the states , , and are allowed. State would cause a repeated visit, and would produce the forbidden sequence left, down, right. Symmetrically, a move left is allowed from exactly , , and . A downward move never violates the direction restriction. It leads from to , from to , and from any other state to . Consequently, every transition in the recurrences is valid, and the last move of every valid path is represented by one of these transitions.
Solution written by GPT6
Downward states in a row depend only on the preceding row. An state depends only on states to its left, while an state depends only on states to its right. Thus, the stated evaluation order always computes predecessor states first. The initial value is correct. Taking the largest valid predecessor distance and adding the distance of one move preserves each state's definition. By induction, every state stores the maximum distance of a valid path ending in that state. Taking the maximum at the destination gives the answer; if every state is unreachable, no valid path exists.
