Задачка по информатике про Героев, обалдел - когда прочитал Опции

[izrukvruki]

Нашел на одном из форумов по программированию, просто поразило, что уже и про любимую игру начали задачки детям придумывать:

"Вобщем, эта задча была дана ученикам на одной из олимпиад по информатике (так в журнале написанно).
В журнале также есть решение этой задачи, но на языке pascal.

Вот и сама задача.

Входной фаил - f.in
Выходной фаил - f.out

Для игры "Heroes of Might and Magic III" генератор случайных карт создает острова, на которых изначально будут расположены герои. Но при случайной генерации карты острова получаются разными по величине. Назовем коэффициентом несправедливости (это выражение мне особо нравится) отношение площади наибольшего острова к площади наименьшего. Необходимо посчитать этот коэффициент. Карта представляет собой прямоугольник, в каждой клетке которого записан 0(вода) или 1(земля). Островом считается множество клеток, содержащих 1, таких, что от любой до любой из них можно пройти по клеткам этого множества, переходя только через их стороны.

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

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

Ну вот и все, господа программеры
Эта задача, как я считаю - хорошая мозгочистка.
Приятных решений, тупиков... и еще стальных вам нервов "

[Darkmoon]

Прочитал, скрипнул своими филологическими мозгами... и ушел пить чай...

[izrukvruki]

я кстате забыл сказать, что написал ее не для решения (ну если кто хочет то пожалуста), а просто что людей проинформировать...

Если модеры посчитают, то ее моно удалить или перенести.

[Docent Picolan]

не удалять не переонить не надо.. пусть повисит и сама заглохнет.

что касается самой темы - забавно. всё-таки ещё раз убеждаюсь,что герои 3 это классика. воспринимается людьми уже как игра в карты или шахматы..

[Darkmoon]

Не... карты немножко не то имхо... Вот шахматы это верно...

[hippocamus]

А алгоритм там не приводится? Случайно? Не помешал бы...

[izrukvruki]

Нет, но вроде написано, что В ЖУРНАЛЕ приведено решение на Паскале, но что это за журнал не нашел...

[Docent Picolan]

Не... карты немножко не то имхо... Вот шахматы это верно...

ну там от карт я имею в виду случайность.. то бишь какой выпадет артефакт или герой в таверне.. это как раз как в картах - какая попадёт - козырная или нет

[gamecreator]

А на самом деле это легкая задачка.

Добавлено ([mergetime]1200420334[/mergetime]):
Могу рассказать как решается.

[izrukvruki]

Давай

[sergroj]

Да, не сложная. Хотя легкой тоже не назвать.

[NickLee]

А на самом деле это легкая задачка.

Согласен

Сводится к тому, что необходимо посчитать количество 1 в прямоугольном массиве. Единственный интерес вызывает составление алгоритма определения неразрывности однушек (земли)...
Решается просто путем нескольких вложенных циклов, только не указано - сколько непрерывных единиц считать островом ?

[sergroj]

А мне, кроме рекурсии, ничего в голову не идет.

[hippocamus]

Рекурсия логичнее всего. А считается за остров наверное даже 1 клеточка. Или самые большие площади по количеству игроков. Т.е. из 15 островов считаются 5, потому что 5 игроков.

[Druin]

Мне тоже

[gamecreator]

На самом деле все решается графами. каждую клетку считаем за вершину. если соседние клетки обе земля, то они связаны. потом ищем количество компонент связности (например, можно закрашивать вершины).

[Bourn]

Островом считается множество клеток, содержащих 1, таких, что от любой до любой из них можно пройти по клеткам этого множества, переходя только через их стороны.

задача действительно простая, насчет перехода по сторонам, разве в героях нельзя ходить по диагонали на соседние клетки?(в том числе на отдельно стоящие)

[Irh]

Да, есть такая несостыковочка.

А от того, что назвать это все графом, легче имхо не становится.... разве что есть уже написанный алгоритм или код, работающий с графами.

[gamecreator]

разве что есть уже написанный алгоритм или код, работающий с графами.

ну определение компонент связности это просто

[Монца]

Замечу, что любую рекурсию можно заменить циклом