Solve BFS grid delivery routing
Overview
This question evaluates proficiency in grid-based graph traversal and shortest-path computation, along with complexity analysis and handling dynamic changes, assessing skills in algorithm design, graph algorithms, and data structures within the Coding & Algorithms domain.
You are given an m×n grid representing a city: 'S' are DashMart stores, 'H' are homes, '.' are roads, and '#' are obstacles. Movement is allowed in four directions on roads only. For each home cell, compute the length of the shortest path to any store; if unreachable, return -1 for that home. Output an array of distances aligned to the list of homes. Provide the algorithm, complexity, and code. Follow-up: if new obstacles are added frequently between queries, explain how you would update distances efficiently without recomputing everything from scratch.