FunctionRacerProblemsRace

Turn the Signposts

HardGraphsPython, JavaScript, TypeScript, Java, C++

Every cell of grid holds a signpost: > points right, < left, v down and ^ up. A walker starts in the top left cell and always steps to the next cell in the direction of the signpost it stands on. A signpost that points off the grid stops the walk.

Before the walk begins you may turn signposts, each to any direction, at a cost of 1 per signpost turned. Return the least cost after which the walker reaches the bottom right cell. The signpost in that last cell does not matter.

Example 1

grid [">>>","<<<",">>>"]
returns 2

The walker runs along the top row. Turning the last signpost of that row down sends it into the middle row, which leads back left. One more turn at the left end sends it down to the bottom row.

Example 2

grid ["><","^^"]
returns 1

Turn the second signpost down. Turning the first one down instead would need a second turn in the cell below.

Example 3

grid [">>v","<<v",">>>"]
returns 0

The signposts already lead to the goal.

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 Graphs problems