A round cleaning robot plans on an occupancy grid: a list of strings grid, where grid[row][col] is '#' for a cell taken by furniture and '.' for free floor (row 0 is the top row). Planning for a disc is awkward, so planners use a trick: shrink the robot to a single point (its centre) and grow the obstacles instead. The cells the robot's centre may occupy form its configuration space.
A free cell becomes forbidden when the distance from its centre to the centre of some '#' cell is at most radius (measured in cells, so neighbours by a side are 1 apart and neighbours by a corner \sqrt{2} apart):
Only '#' cells are obstacles here: the edge of the map is open floor that continues beyond it.
Write inflate(grid, radius) that returns the inflated map as a list of strings of the same shape: '#' where the grid has an obstacle, '+' for a free cell that the inflation forbids, and '.' for the cells where the robot's centre may still go.
Examples
Input: grid = [".....",
"..#..",
".....",
"....."], radius = 1
Output: ["..+..",
".+#+.",
"..+..",
"....."]
Explanation: the four side neighbours are exactly 1 away, the corner neighbours 1.414.
Input: grid = [".....",
"..#..",
".....",
"....."], radius = 1.5
Output: [".+++.",
".+#+.",
".+++.",
"....."]
Press Run with print("\n".join(inflate(warehouse(12, 30, 1), 1.5))) to see a whole floor: the setup provides warehouse(rows, cols, seed, shelves=8), which builds a random plan of rectangular shelves; the larger tests use it.
Constraints
- all rows have the same length
Goals
- Grow every obstacle by the robot's radius, so the robot can be planned for as a single point
- Use the distance between cell centres, with the boundary case stated