Как реализовать алгоритм расстановки кораблей на поле?

Question

[Данил Антошкин]

Добрый день хочу узнать как написать алгоритм расстановки кораблей чтобы они не прикасались друг к другу ?

Поле 10x10 это двухмерный массив из символов

Корабли из обычного морского боя :

4 клетки
3 клетки
2 клетки
1 клетка

Answer 1

[Alexander Litvinenko]

Требуется случайная генерация?

1. определяешь случайным образом положение корабля
2. исключаешь занятые клетки с массива, если места нет а корабли есть - обнуляешь поле.
3. идешь к пункту 1, пока не расставишь все корабли.

Answer 2

[Saboteur]

Какой-то слишком общий вопрос. Вы непонимаете, как делать проверку на соседние пустые клетки в двумерном массиве?

Создаете функцию, где по циклу или отдельными проверками делаете так:

if (myarray[x+1,y]==1)
{
return false;
}

и проверяете для всех нужных размеров. Сократить тут можно немного.

Comments

[Данил Антошкин]

вы проверяете только одну клетку рядом а если надо проверить 8 вокруг корабля ? И все корабли находиться в разных местах, то что делать в этом случаи ?

[Saboteur]

>и проверяете для всех нужных размеров. Сократить тут можно немного.

то есть вам нужно будет сделать проверку всех точек, и для каждого корабля учесть, что он должен продолжаться. Тут нет какого-то волшебного алгоритма. Нужно просто проверить ВСЕ точки.

Answer 3

[Sumor]

Самое главное, что в классическом морском бое, если расставлять корабли начиная с 4-х палубного, затем два 3-х палубных, затем три 2-х палубных и четыре однопалубных, то всегда существует расстановка кораблей. Это легко доказуемо. Если вы начнёте с однопалубных, то можете попасть впросак.
Четырёхпалубный ставится выбором направления - горизонталь/вертикаль и выбор начальной клетки - всего 140 вариантов.
Помечаете занятые клетки, клетки вокруг корабля и приступаете к трёхпалубным.
Пробегаете незанятые клетки и пытаетесь проверить возможность поставить корабль по горизонтали или вертикали. Сохраняете в массив все возможные варианты, а затем выбираете один случайным образом.
Повторяете пока не будут расставлены все корабли. Доказательство существования расстановки гарантирует, что у вас всегда будет место, куда поставить корабль.