количество вариантов расположения кораблей на игровом поле, морской бой Опции

[LLL]

Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)

на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле.

[andriano]

Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями.
Оцениваем: (8*13)^4~117000000.
Многовато.
В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться.
Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением.
Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции.

[Lapp]

Это либо 4 32-разрядных числа, либо 2 регистра ММХ.

andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом?
Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))

Ответ получился такой: 64998706.
Я только не уверен, правильно ли будет выкладывать тут код олимпиадной задачи.. LLL, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память.

[andriano]

andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом?
Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))

Не знаю, у кого как, но у меня, если программа при отладке выполняется больше некоторого времени, это начинает вызывать дискомфорт. Причем для меня лично этот временной порог составляет около 2-х секунд.
Полминуты в моем представлении - больше двух секунд.
Это во-первых.
Во-вторых: прежде чем рещать какую-то потенциально ресурсоемкую задачу я пытаюсь оценить максимальное время, которое она может выполняться. На мой взгляд, это естественно.
Если программа потенциально ресурсоемка, я сразу пытаюсь написать ее достаточно оптимально по времени. Т.е. архитектура программы строится так, чтобы не было излишних потерь времени в критичных местах. На мой взгляд это также естественно. Гораздо более естественно, чем переписывать программу с нуля, когда окажется, чт она чрезвычайно ресурсоемка, а реализованный подход не позволяет ее существенно ускорить.
И вообще, процесс предварительного проектирования (до того, как будет написана первая стргочка кода) - достаточно важный этап, на который молодые программисты обычно не обращают внимание. А зря.

PS. А насчет ускорения асфальтового катка - афористично.

Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек).
Но ведь е любая задача поддается масштабированию.

Сообщение отредактировано: andriano - 10.11.2009 13:47

[Lapp]

Спасибо))

Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек).
Но ведь е любая задача поддается масштабированию.

Я начал с 4x4 при максимальной длине корабля L=1 (одна опечатка в границах была поймана на этом уровне). Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)). Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).

[andriano]

Спасибо))
Я начал с 4x4

Просто споткнулся об это утверждение.
Даже не дочитав до конца фразы. И только дочитав:

при максимальной длине корабля L=1

понял, то такое возможно.

(одна опечатка в границах была поймана на этом уровне).

А я бы вообще не стал делать проверки на границах.
Во-первых, граничные ячейки вообще рассматривать бессмысленно - в них по условию ничего нельзя поставить, а во-вторых, при определенной длине корабля можно сразу вычислить пределы циклов, в которых его можно двигать.
Например, на поле 7х6 и горизонтальном положении 4-х палубного корабля его можно двигать лишь в пределах от 1 до 2 клетки (нумерация с 0) по горизонтали и от 1 до 4 - по вертикали, а при вертикальном положении - от 1 до 5 по горизонтали, а по вертикали вообще двигать нельзя.

Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)).

Почему вслух? Так надежнее, или время быстрее идет?

Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).

О ММХ я лишь упомянул, все дальнейшие рассуждения исходят из использования 32-разрядных чисел.
И, кстати, это также является примером подхода, которого я придерживаюсь: на этапе проектирования предусматривается возможность перехода на другую систему команд, но сначала задача пишется с использованием лишь стандартных средств и лишь потом, при необходимости, применяется дополнительная ассемблерная оптимизация.

Сообщение отредактировано: andriano - 10.11.2009 14:30

[Lapp]

> только дочитав:понял, то такое возможно.
)) не только возможно прогнать, но (главное!) возможно предстказать результат)).

> А я бы вообще не стал делать проверки на границах.
> Во-первых, граничные ячейки вообще рассматривать бессмысленно
Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю..

> Почему вслух? Так надежнее, или время быстрее идет?
привычка. Я так делаю всегда (например, на кухне, если надо, вместо таймера). Это позволяет некоторую многозадачность - слышишь свой голос и проще не сбиться, даже если отвлечешься)).

> О ММХ я лишь упомянул,
Я тоже))

Похоже, LLL решила забить на ответы.. Была тут на форуме утром, но.. LLL, уважаемая, ты слышишь, что тут люди, которых ты просила помочь, пытаются с тобой говорить? Ау-у! не понимаю людей, которым жалко лишний раз по клаве пройтись..

[andriano]

Я их рассматривал... скажем так: наполовину. Цикл расстановки кораблей только по внутренним клеткам (минус хвост). Но цикл проверки столкновения - по всему полю. Именно это означают мои слова "без отсечения" в первом мессадже. Отсечение усложнило бы немного логику, а вот ускорило ли бы - не знаю..

Так и не понял про отсечение.
Но все по порядку.

"Минус хвост", если я не ошибаюсь, означет, что верхний предел цикла уменьшается на длину хвоста? Или "минус хвост" означает что на этапе конструирования цикла хвост никак не учитывается?

Проверка столкновения по всему полю - иначе никак. Здесь чтобы учесть невозможность соприкосновения кораблей нужно что-то снабдить дополнительным рядом граничных клеток, либо новый корабль, либо совокупность уже расставленных. Т.е корабль, скажем, 3-палубный, представляется прямоугольником 3х5 клеток.

И что, все-таки, такое - отсечение?


Добавлено через 3 мин.

А может всётаки перенесёте тему в раздел задач, к игре она ведь имеет только косвненное отношение...
А ММХ это что?

Отчего же?
Здесь рассматриваются алгоритмы характерные именно для игр и подходы характерные для них же.
А по поводу ММХ: http://ru.wikipedia.org/wiki/MMX (между прочим, первая же ссылка в Гугле по запросу "MMX")
Хотя в статье есть ряд неточностей (если не сказать, откровенно ложных утверждений).

Сообщение отредактировано: andriano - 10.11.2009 15:26

[Lapp]

"Минус хвост", если я не ошибаюсь, означет, что верхний предел цикла уменьшается на длину хвоста? Или "минус хвост" означает что на этапе конструирования цикла хвост никак не учитывается?

Первое. Цикл по координатам "носа корабля".

Т.е корабль, скажем, 3-палубный, представляется прямоугольником 3х5 клеток.

При постановке - да, конечно. Потом - нет.

И что, все-таки, такое - отсечение?

Это значит при проверке столкновения не залезать на прибрежную зону. Проверка на столкновение ведется в цикле. Соответственно, нужно корректировать границы цикла. Учитывая. что граница пропорциональна примерно корню из площади (количества внутренних клеток), это вряд ли целесообразно.

Мммм.. сейчас подумал, что ведь есть же другой способ... думаю, он побыстрее будет. ээ.. Вот, все же интересно - надо еще это автору темы?

Здесь рассматриваются алгоритмы характерные именно для игр и подходы характерные для них же.

... но все же не игра! Думаю, RathaR прав. Возиться лень.. ))

(sorry about that mess.. забыл перейти в другое окно и стал нажимать всякие клавиши; эффект был забавный..)