![]() |
![]() |
LLL |
![]()
Сообщение
#1
|
Группа: Пользователи Сообщений: 1 Пол: Женский Репутация: ![]() ![]() ![]() |
Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)
на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле. |
![]() ![]() |
andriano |
![]()
Сообщение
#2
|
Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: ![]() ![]() ![]() |
Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями.
Оцениваем: (8*13)^4~117000000. Многовато. В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться. Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением. Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции. |
![]() ![]() |
![]() |
Текстовая версия | 9.07.2025 8:01 |