Find shortest path in a grid with obstacles

Q: Find shortest path in a grid with obstacles

This question evaluates understanding of pathfinding in grid-based environments, graph traversal concepts, and algorithmic complexity when navigating obstacles and boundary constraints in an unweighted 2D search space.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a 2D grid of size m x n representing a maze. Each cell in the grid is either empty (0) or blocked (1).

You are also given two coordinates:

start = (sx, sy)
end = (ex, ey)

You can move from a cell to its 4-directional neighbors (up, down, left, right), but you cannot move into or through blocked cells, and you must remain inside the grid.

Return the length of the shortest path (in number of steps) from start to end. If there is no valid path, return -1.

Assumptions and details:

0 <= sx, ex < m
0 <= sy, ey < n
grid[sx][sy] == 0 and grid[ex][ey] == 0
1 <= m, n <= 10^3
Time complexity should be efficient for the upper bounds (you may consider BFS or DFS-based approaches).

Input format (for reference):

m, n (integers)
grid as an m x n matrix of 0s and 1s
start coordinate
end coordinate

Output:

An integer representing the length of the shortest path, or -1 if unreachable.

Find shortest path in a grid with obstacles

Overview

Comments (0)