Hackerland Safe Path

Problem Statement

Hackerland Safe Path Problem Description The city of Hackerland is a two-dimensional grid of size `n x m`. Each cell is one of: `.` — an empty cell, `*` — a cell containing an obstacle, `S` — the starting point (there is exactly one), `E` — the ending point (there is exactly one). One can move in four directions: up, down, left and right, between cells that share a side. A **path** is a sequence of cells starting at `S` and ending at `E` in which consecutive cells are neighbours and no cell is visited more than once. For a cell `(r, c)`, its **clearance** is the smallest Manhattan distance from that cell to any obstacle cell in the grid. The distance between two cells `(r1, c1)` and `(r2, c2)` is `|r1 - r2| + |c1 - c2|`, where `|a|` is the absolute value of `a`. The **safety of a path** is the smallest clearance among all cells on that path, including `S` and `E` themselves. Move from `S` to `E` so that the safety of the path is as large as possible, and return that largest possible sa