Долго читаю, но на волне взаимопомощи решил зарегистрироваться. Работаю java разработчиком, могу помочь разъяснить какую-нибудь тему или помочь понять куда двигаться по обучению, поревьюить код или просто как-то пообщаться вживую если потребуется
Хз, сейчас 3 часа ночи и моя голова не особо работает но я бы рассуждал так:
4х палубник может занять максимум 6*3 = 18 клеток
3х палубники могут занять 5*3*2 = 30 клеток
2х палубники занять 4 * 3 * 3 = 36 клеток
1 палубники занимают 9*4 = 36 клеток
Итого: всего максимальная допустимая поверхность 120 клеток, это на 20 клеток больше обычного поля (10 х 10). Нужно избавиться от оверхеда за 10 кораблей
В итоге я бы делал что-то костыльно ориентированное.
Сначала бы я ставил 4х палубник в случайную точку. .
Если кораблей остается <4-8 а оверхед еще есть, то старался бы лепить корабли с граничными зонами, пока оверхед не пропадет.
Держите корабли (их длинну) и вытаскивайте случайные по длинне от 2х до 3х, это нужно чтобы избежать моментов когда однопалубники встанут неудобно.
Мб завтра со свежей головой придумаю более оптимальное решение, но пока что в голову приходит только нечто подобное чтобы решать в лоб
Тогда я подумаю над алгоритмом и отпишу ближе к концу недели, на это нужно отвлечься на часик-два :)
Пардон за задержку. Выходные были довольно оживленными поэтому пораскинув мозгами попытался нарисовать полностью забитое поле (worst case scenario). Пораскидав варианты я понял что при заполнении рандомом кораблями от большего к меньшему - скорей всего никогда не получится заполнить поле таким образом чтобы мы под конец не смогли поставить корабль.
Алгоритм примерно такой:
Общая идея:
-Корабли выставляем от большей палубы к меньшей.
-Сначала определяем горизонтальный или вертикальный корабль.
-Если хоть как-то обкакаемся - попробуем рефрешнуть доску и начать с начала (хотя, скорей всего, можно доказать что при таком алгоритме это никогда не вызовется)
Выбор случайной точки:
-Выбираем случайную точку из промежутка (10x10-n, где n-кол-во палуб корабля (микрооптимизация можно этого не делать))
-Пытаемся посмотреть можно ли поставить корабль (сверяемся является ли точка == 0, являются ли еще n-1 точек слева/снизу == 0 или не выходят ли они за пределы поля.
-Если алгоритм не успешный сдвигаем клетку на одну влево (если дойдет до границы то на одну вниз и с начала ряда)
-Если все еще не удалось - то делаем то же самое только вправо и вверх
-Если ничего не получилось (скорей всего не валидный кейс) меняем ориентацию корабля (горизонтальный/вертикальный)
Как поставить корабль:
-Если точка валидная то можно начать ставить корабль. Ставим в ячейку массива цифру 1. Все прилягающие клетки помечаются цифрой 2, дальше помечается след. клетка массива.
-После построения всех кораблей нужно будет пробежаться еще раз по всем полям и заменить все 2ки на нули обратно (чтобы красиво отобразить поле.
Помощники
236 постов785 подписчиков
Правила сообщества
Нельзя обсуждать Политику.
Ругаться и оскорблять.