Предположим на мгновение, что вы можете хранить всю информацию в памяти наивным способом.
Ваша доска имеет размер N x M, и есть S кораблей произвольного размера.Я собираюсь сделать некоторые предположения:
- Корабли имеют прямоугольную форму.Было бы достаточно легко учесть корабли неправильной формы, но о прямоугольнике легче говорить.
- Стороны кораблей параллельны линиям сетки.Опять же, было бы достаточно легко учесть произвольную ориентацию.
Вы представляете свой корабль как:
Ship
Id
Top
Left
Width
Height
Hits // array of [Height x Width] Booleans that indicates which positions have been hit.
HitCount // number of positions that have been hit. When HitCount == (Width x Height), the ship is sunk.
А ваша доска представляет собой массив ссылок N x M насудов.Таким образом, доска 5 х 4 с двумя кораблями может выглядеть так:
0 1 2 3 4
0 ship1 ship1 ship1 NULL NULL
1 ship1 ship1 ship1 NULL ship2
2 NULL NULL NULL NULL ship2
3 NULL NULL NULL NULL ship2
Теперь кто-то делает снимок в строке 1, столбец 3. Вы смотрите в массив и видите, что в этом квадрате нет корабля.,Чистая мисс.Следующий снимок идет в (2, 4).Вы индексируете в массив и видите, что это корабль 2. Вы ищите корабль 2, переводите позицию доски (2, 4) в массив корабля Hits (в данном случае это будет (0, 1), и записываетеУдар. Увеличивайте HitCount, если эта позиция не была ранее поражена. Когда HitCount == (Width x Height), корабль потоплен.
Это представление позволяет осуществлять прямой поиск при каждом выстреле: поиск не требуется.асимптотические термины, это требует O ((N x M) + S) памяти, а обработка выстрела O (1). На самом деле, наихудший случай памяти составляет 2*(N x M), потому что для каждого корабля требуется Height*Width памяти, а вв худшем случае корабли могут заполнить всю доску.
Дело в том, что если у вас достаточно памяти для представления всей структуры данных, то поиск очень эффективен и не зависит от размера платы иликоличество кораблей.
Вы можете уменьшить объем памяти структуры выше, используя несколько простых приемов. Используя массив битов или что-то подобное, вместо массива логических значений для Hits, например, может сэкономить вам место.А хранение кораблей в массиве и использование индекса, а не ссылки на доске, может сократить пространство, используемое для доски, вдвое.Но даже с оптимизацией памяти эта структура может зайти так далеко.При 16 гигабайтах оперативной памяти максимальный размер платы, вероятно, будет порядка 100 000 x 100 000.
Если вам действительно нужна плата размером миллиард на миллиард с миллионами кораблей произвольного размера, представительствовыше бы занял огромное количество памяти.Сама доска будет 2 ^ 60 клеток.Вы должны проявить творческий подход к использованию разреженных структур данных, но поскольку корабли могут иметь произвольный размер, вам придется учитывать наихудший случай: корабли занимают столько места, что разреженная структура данных не даетэкономия.В конце концов вам нужно будет создать представление, которое может распространяться на диск или распределяться по нескольким машинам в массивном кластере.