Страница: 1 [Всего задач: 1]      

Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные
В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

Пример входного файла
7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0

Пример выходного файла
2.66667

Прислать комментарий

Решение

Страница: 1 [Всего задач: 1]