Compute shortest path with obstacles

Q: Compute shortest path with obstacles

This question evaluates proficiency in graph algorithms and grid-based shortest-path computation, including handling weighted cells and obstacles and familiarity with Dijkstra-style shortest-path techniques.

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 an m×n grid with nonnegative cell costs and blocked cells marked '#'. You may move up, down, left, or right. Given start (sx, sy) and target (tx, ty), compute the minimum total cost path that avoids obstacles, or return -1 if unreachable. Implement an O(mn log mn) solution using Dijkstra’s algorithm with a priority queue, and explain how you would reconstruct the path.

Compute shortest path with obstacles

Overview

Comments (0)