Compute nearest dashmart and busiest assignments
Overview
This question evaluates understanding of graph traversal and shortest-path computation on grids with obstacles, plus the ability to combine distance-based scoring and deterministic tie-breaking heuristics; it is categorized under Coding & Algorithms and emphasizes practical application of algorithmic concepts.
You are given an m x n grid of characters where 'D' marks a dashmart, 'X' marks an impassable cell, and ' ' (space) marks a passable cell. Movement is allowed only in four directions (up, down, left, right) and cannot go outside the grid or into 'X'. You are also given a list of K query locations (row, col). Part A: For each query location, return the length (in steps) of the shortest path to any dashmart. If the starting cell is a dashmart, the distance is 0. If the starting cell is 'X' or no path to any dashmart exists, return -1. Implement a function nearestDistances(grid, queries) that handles multiple test cases and is bug-free. Part B (follow-up): Each dashmart at coordinates (r, c) has a non-negative base busy score B[r][c] (provided for all 'D' cells) and you are given an integer alpha ≥ 0. Define the effective busy of a dashmart for a location at grid distance d as max(0, B[r][c] - alpha * d). For each query location, among all reachable dashmarts, return the dashmart that maximizes effective busy; break ties by smaller distance d, then by smaller row, then by smaller column. If no dashmart is reachable, return (-1, - 1). Also return the chosen dashmart’s effective busy value for that location.