![]() |
![]() |
LLL |
![]()
Сообщение
#1
|
Группа: Пользователи Сообщений: 1 Пол: Женский Репутация: ![]() ![]() ![]() |
Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)
на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле. |
![]() ![]() |
andriano |
![]()
Сообщение
#2
|
Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: ![]() ![]() ![]() |
На самом деле, раз корабли не могут соприкасаться, при переборе просто нужно вместе с установкой корабля, делать занятыми клетки вокруг него.
Ну и сам перебор, естественно вести в диапазоне (M-1, N-2) клеток. Для увеличения скорости перебора я бы каждому полю ставил в соответствие 1 бит, тогда, учитывая, что максимальные 15 клеток укладываются в 16-разрядный регистр, просмотр всего поля состоял бы всего из 10 операций сравнения. Можно, использую 32-разрядные регистры, сократить количество операций до 5 или MMX - до трех. |
![]() ![]() |
![]() |
Текстовая версия | 9.07.2025 13:36 |