Conveyor Grid Fixes
MediumAdvanced Graphs
Problem
A sorting floor is a grid of conveyor tiles. grid[r][c] says where the tile pushes a parcel: 1 right, 2 left, 3 down, 4 up. A parcel dropped on the top-left tile follows the arrows for free.
A technician can turn any tile to point in another direction for a cost of 1 per tile (each tile is turned at most once). Return the minimum cost so that a parcel dropped at the top-left tile reaches the bottom-right tile. Arrows pointing off the grid simply stop the parcel.
Example 1
- Input:
- grid = [[2,2],[1,2]]
- Output:
- 1
Turn the top-left tile down (cost 1); the parcel lands on a right arrow that carries it to the goal.
Example 2
- Input:
- grid = [[1,1,3],[4,2,3],[1,1,1]]
- Output:
- 0
right, right, down, down already reaches the goal.
Example 3
- Input:
- grid = [[4]]
- Output:
- 0
Constraints
- 1 ≤ rows, cols ≤ 100
- grid[r][c] ∈ {1, 2, 3, 4}
Hint
Show the first hint
Model each tile as a node. Moving the way its arrow points costs 0; moving any other way costs 1.
Walkthrough
How to approach it
01Clarify before coding
- Can a tile be turned more than once? No, and an optimal route never visits a tile twice anyway.
- Does turning a tile cost the same whatever the new direction? Yes, 1.
- Is the start the same as the goal on a 1 × 1 grid? Yes: cost 0.
02Brute force
Try every assignment of directions to tiles and simulate the parcel.
Cost: 4^(R·C) assignments: astronomically large.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.