|
Название задачи: Острова . |
 |
Условие
Генератор случайных карт известной игры 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
Решение
Скачать архив тестов и решенийНа первый взгляд задача кажется совершенно стандартной, однако указанные в условии ограничения не позволяют решить ее привычным способом. Можно, конечно, попытаться разместить матрицу 1000 × 1000 в динамической памяти побитово и написать нерекурсивный вариант процедуры ее просмотра, чтобы не происходило переполнения стека. Этот способ приведет к успеху, однако мы рассмотрим более красивое решение данной задачи.
Будем просматривать матрицу по строчкам сверху вниз. В каждый момент времени храним в памяти только текущую и предыдущую строчки матрицы. Также будем помнить максимальный и минимальный размеры островов, которые мы уже полностью просмотрели, текущие размеры островов, которые мы видим в данный момент, а для каждой единички в строках, которые мы просматриваем, – к какому острову она относится. Единичка (или группа единичек, стоящих подряд) в текущей строке может быть:
1. Началом нового острова, если сверху (т.е. на той же позиции в предыдущей
строке) от всех единичек стоят ноли. Например,
1 0 0 0 0
0 1 1 0 1
2. Продолжением какого-то острова, начавшегося в предыдущей строке или
раньше, если хотя бы над одной из единичек группы стоит единичка. Например,
0 1 0 0
0 1 1 0
3. Одна группа единичек может служить продолжением сразу нескольких
островов. Тогда эти острова объединяются (т.е. далее рассматриваются как один
остров), а их текущие площади складываются. Например,
0 1 0 1 0
1 1 1 1 1
В этом случае при просмотре первой строки две единички будут
рассматриваться как самостоятельные острова, а при рассмотрении второй
строки «объединятся» в один остров. Однако, в следующем случае:
1 1 1 1
1 0 0 1
1 1 1 1
при рассмотрении третьей строки не нужно производить объединение островов,
потому что эти единички принадлежат одному и тому же острову (т.к. при
переходе от первой строки ко второй они являлись соседями единичек,
принадлежащих одному острову).
