LeetCode-Style Coding Practice | Dataford Interview Questions

Cruise's local planner represents a small driving area as a rectangular grid. A vehicle can move up, down, left, or right through open cells, and it may pass through at most one blocked cell when that cell represents a temporarily uncertain obstacle. Find the minimum number of moves from the start cell to the destination, or return -1 if no valid route exists.

You may not leave the grid. The start and destination are open cells.

Formal Specification

Implement shortest_route(grid), where grid is a list of equal-length strings. Each character is either S for the start, G for the goal, . for an open cell, or # for a blocked cell. Return an integer containing the minimum number of moves, counting each transition to an adjacent cell as one move. The route may use zero or one blocked cell. Return -1 when the goal cannot be reached.

Constraints

1 <= rows, columns <= 500
The grid contains exactly one S and one G
Every row has the same length
Each cell is S, G, ., or #
The start and goal cells are open
Return the minimum number of moves or -1

Function Signature

def shortest_route(grid):

Your question is LeetCode-Style Coding Practice. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem