Maximum Minimum Distance from Obstacle

Problem Statement

Maximum Minimum Distance from Obstacle Problem Description The city of Hackerland can be represented as a two-dimensional grid of size n x m. Each cell is either empty (a dot character '.'), has an obstacle (an asterisk '*'), an S, or an E that represent the start and end points, respectively. You can move in four directions: up, down, left, and right. Your goal is to find a path from the starting point to the ending point such that the minimum distance from any obstacle along the path is as large as possible. Return this maximum possible minimum distance. The distance between any two points on the grid with coordinates (r 1 , c 1 ) and (r 2 , c 2 ) is calculated as |r 1 - r 2 | + |c 1 - c 2 |, where |a| is the absolute value of integer a. Notes: One can visit a cell with an obstacle if necessary, i.e., no other path exists. A cell can be visited only once. Examples Example 1: Consider the following grid of size 4x4: S . . * . . . . . * . . . . . E The optimal path is shown in the 'Cel