Новый Морской бой Опции

[bLACK_wINGS]

В общем.. ига такая на логику... Весь инет облазил в поисках инфы, ничего не нашел.. попалась случайно вместе с журнальчиком 777. Суть игры:
Дано поле. По вертикали и горизонтали расположены числа 0..9. Каждое число предполагает наличие в в линии такого количества фрагментов кораблей. Набор кораблей стандартный. В общем прожка по идее должна выдать расстановку кораблей. Ваши соображения по поводу))))

[Michael_Rybak]

Я бы попробовал такой перебор.

Рассмотрим пустую строку, для которой сумма, например, равна 2.
Существует С из 10 по 2 = 10*9/2 = 45 способов закрасить строку таким способом.

Вообще, из N клеток закрасить К всегда можно С из N по К способами.

Так вот, выбираем строку/столбец, для которой количество вариантов минимально.
Перебираем все варианты, и для каждого из них делаем выводы, а именно: если, например, в горизонтальной строке встречаются 2 подряд фрагмента, обрамленные пустыми клетками, то это - не что иное, как двухпалубный корабль. Обрамляем его пустыми клетками сверху и снизу. Если же встречается один фрагмент, то это - либо 1-палубный, либо вертикальный, поэтому в любом случае ставим прочерк в соседние по диагонали клетки.

А теперь выбираем следующую строку/столбец, в которой количество вариантов минимально, но уже учитываем поменявшуюся обстановку на поле. Например, если в строке записана сумма 8, но уже известно, что одна (определенная) клетка там - пустая, а другая - фрагмент корабля, то здесь у нас уже не С из 10 по 8, а С из 8 по 7.

Перебирая варианты нужно, конечно, считать встретившиеся корабли, чтобы вовремя сделать откат противоречивого варианта.

Для удобства откатов лучше хранить не матрицу состояний (0 - не знаем, 1 - фрагмент, 2 - пусто), а матрицу целых чисел (0 - не знаем, -1 - фрагмент, K>0 - пусто, причем является результатом К выводов).

Тогда, когда мы в некоторую клетку ставим -1, мы должны просто инкрементировать всех соседей по диагонали, тем самым обозначая, что там - пусто (при этом проверяя отсутствие противоречий), а для отката достаточно будет просто декрементировать обратно, а не запоминать и восстанавливать все 8 соседей.


Должно работать быстро. Если будут проблемы с реализацией - маякни, если будет время, было бы интересно закодить

Сообщение отредактировано: Michael_Rybak - 9.10.2006 0:48