Problem 572557 · medium · Robotics · Level 05 Planning and Mapping

Keep Off the Walls

cost map · Dijkstra's algorithm · clearance · weighted grid

A museum guide robot could squeeze past the display cases, but a route that brushes every case makes the curators nervous. Its planner therefore uses a cost map: each cell has a price for entering it, higher near obstacles.

The map is a list of strings grid: grid[row][col] is '#' for a display case and '.' for floor (row 0 at the top). For a floor cell, let d be the distance from its centre to the centre of the nearest '#' cell (side neighbours are 1 apart, corner neighbours \sqrt2; d is infinite when the map has no '#' at all). Entering that cell costs

\text{cost} = 1 + \max(0,\ \text{safe} - d)

so cells at least safe away cost 1, and closer cells cost more: a cell right beside a case (d = 1) costs safe when safe >= 1. The robot moves up, down, left or right onto floor cells; it never enters a '#'. The price of a route is the sum of the costs of every cell it enters: the goal counts, the start does not.

Write cheapest_route_cost(grid, start, goal, safe) that returns the smallest price of a route from start to goal, or None if the goal cannot be reached. A route from a cell to itself costs 0.0.

Examples

Input:  grid = [".....",
                "..#..",
                ".....",
                "....."], start = (2, 0), goal = (2, 4), safe = 2
Output: 6.0
Explanation: straight along row 2 costs 1.586 + 2 + 1.586 + 1 = 6.172 (the cells
beside the case are 1.414, 1 and 1.414 away). Stepping down to row 3, across and back
up takes 6 moves, but every cell on the way is at least 2 away and costs 1.

Input:  the same grid, start and goal, safe = 1.5
Output: 4.67157287525381
Explanation: now the straight route costs 1.086 + 1.5 + 1.086 + 1, cheaper than the detour.

The setup provides warehouse(rows, cols, seed, shelves=8) and aisles(rows, cols, seed, gap=3, clutter=0), two random floor plans the larger tests use. Press Run with print("\n".join(aisles(20, 30, 1))) to see one.

Constraints

  • all rows have the same length; start and goal are floor cells
  • grids up to 60 by 60; floats are compared with a tolerance of 1e-6

Goals

  • Build a cost map that charges more for cells close to obstacles
  • Find the cheapest route rather than the shortest one
  • See a detour win when hugging a wall is expensive
Starting Python…