Islands#3062
The random map generator in the popular game Heroes of Might and Magic III creates islands where heroes are initially placed. These islands can vary in size. We define the coefficient of unfairness as the ratio of the area of the largest island to the area of the smallest island. Your task is to calculate this coefficient.
The map is represented as a rectangle of size N \times M, where each cell contains either the digit (representing water) or the digit (representing land). An island is defined as a maximal connected group of cells containing ones, that is, a group such that:
From any cell in , you can reach any other cell in by moving only through adjacent cells in (sharing a side).
Adding any other cell containing to would break this connectivity condition.
The first line of the input contains the integers and , which specify the dimensions of the map (1 \leq N, M \leq 1000). The map itself follows, consisting of rows, each containing numbers ( or ) separated by spaces.
Output the coefficient of unfairness, formatted to decimal places. If there are no islands on the map, output 0.
Example 1