Problem Statement

Safest Route Through Hackerland The city of Hackerland is a two-dimensional grid of size n x m . Every cell is one of four things: . an empty cell, * an obstacle, S the starting point, E the ending point. There is exactly one S and exactly one E , and at least one * . You travel from S to E moving one step at a time in four directions: up, down, left and right. Obstacles do not block you - you may step onto a cell that holds an obstacle if that is what the route demands - but a cell may be entered at most once. For any cell of the grid, its clearance is the distance to the nearest obstacle. The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2| , where |a| is the absolute value of a . The clearance of a route is the smallest clearance among all the cells it visits, including S and E . Choose the route whose clearance is as large as possible and return that clearance. Input Format The first line contains the integer n , the number of rows. Each of the next n lines