на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле.
Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями. Оцениваем: (8*13)^4~117000000. Многовато. В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться. Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением. Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции.
Это либо 4 32-разрядных числа, либо 2 регистра ММХ.
andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом? Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))
Ответ получился такой: 64998706. Я только не уверен, правильно ли будет выкладывать тут код олимпиадной задачи.. LLL, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память.
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой
andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом? Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. ))
Не знаю, у кого как, но у меня, если программа при отладке выполняется больше некоторого времени, это начинает вызывать дискомфорт. Причем для меня лично этот временной порог составляет около 2-х секунд. Полминуты в моем представлении - больше двух секунд. Это во-первых. Во-вторых: прежде чем рещать какую-то потенциально ресурсоемкую задачу я пытаюсь оценить максимальное время, которое она может выполняться. На мой взгляд, это естественно. Если программа потенциально ресурсоемка, я сразу пытаюсь написать ее достаточно оптимально по времени. Т.е. архитектура программы строится так, чтобы не было излишних потерь времени в критичных местах. На мой взгляд это также естественно. Гораздо более естественно, чем переписывать программу с нуля, когда окажется, чт она чрезвычайно ресурсоемка, а реализованный подход не позволяет ее существенно ускорить. И вообще, процесс предварительного проектирования (до того, как будет написана первая стргочка кода) - достаточно важный этап, на который молодые программисты обычно не обращают внимание. А зря.
PS. А насчет ускорения асфальтового катка - афористично.
Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек). Но ведь е любая задача поддается масштабированию.
Кстати, я уверен, что отлаживал задачу ты отнюдь не на поле 15х10, а значитаельно меньше - на таком, которое по твоим оценкам даже в наихудшем случае решение не заняло бы много времени (я бы начал с поля 7х8 ячеек). Но ведь е любая задача поддается масштабированию.
Я начал с 4x4 при максимальной длине корабля L=1 (одна опечатка в границах была поймана на этом уровне). Продолжил при 5х5 и L=2, а затем 6х7 и L=3 (с просмотром картинок). С реальными параметрами запустил два раза - второй раз считал вслух)). Конечно, все это естественно, что ты сказал.. Но ты забыл, что задача - олимпиадная, и у тебя очень ограниченное время на решение. Плюс убежденность, что ММХ (в десятом-то классе) вряд ли потребуется)).
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой