How should I practice Shortest Path Around Rectangular Obstacles?

Start by reading the full statement, solve the visible examples, then compare the pattern against related DRW online assessment problems in FastPrep.

Is Shortest Path Around Rectangular Obstacles associated with DRW?

FastPrep tags this as a DRW online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Shortest Path Around Rectangular Obstacles

Learn this problem

● Medium

DRWNEW GRADOA

Problem statement

You are given an N by M grid of cells. A cell has coordinates (x, y), where 0 <= x < N and 0 <= y < M.

There are K axis-aligned rectangular obstacles. Rectangle i covers every cell whose coordinates satisfy X1[i] <= x <= X2[i] and Y1[i] <= y <= Y2[i]. Covered cells are blocked, and rectangles may overlap.

Start at (0, 0). In one step, you may move to an unblocked cell directly above, below, left, or right of your current cell. Return the minimum number of steps needed to reach (N - 1, M - 1).

Return -1 if no such path exists. In particular, return -1 when the start or destination cell is blocked.

Function

solution(N: int, M: int, X1: int[], Y1: int[], X2: int[], Y2: int[]) → int

Examples

Example 1

N = 6M = 4X1 = [2,1,4]Y1 = [0,1,3]X2 = [2,3,4]Y2 = [2,1,3]return = 10

One shortest route is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (1,3) -> (2,3) -> (3,3) -> (3,2) -> (4,2) -> (5,2) -> (5,3). It uses 10 steps and avoids every blocked cell.

Constraints

N and M are positive integers.
X1, Y1, X2, and Y2 have the same length K; K may be zero.
For every i, 0 <= X1[i] <= X2[i] < N and 0 <= Y1[i] <= Y2[i] < M.
Rectangle coordinates are zero-indexed and inclusive.