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

[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, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память.