Как смоделировать тип данных сетки?

Question

Как наилучшим образом смоделировать сетку (проблема тральщика) как тип данных?Лучше ли использовать вектор как двухмерный объект.Причиной появления вектора является возможность проверки границ.Правильно ли мое предположение?

Спасибо :)

Answer 1

Поскольку размер сетки фиксирован (я полагаю!), Вектор дает вам небольшое преимущество перед массивом.Поэтому я рекомендую использовать 2D-массив.

Хотя это и не нужно, может оказаться полезным добавить значения часового вокруг границы сетки, чтобы устранить необходимость неявной проверки границ.Примером является размещение 0 вокруг сетки, когда вы суммируете количество соседних мин.Прочитайте эту статью , чтобы начать с простых примеров.

Answer 2

Лично я считаю, что вариант жилета - использовать специализированный класс, который действует как многомерный массив, давая вам преимущества вектора STL (с учетом размера, без неявных преобразований в указатели и т. Д.). Класс Boost multi_array может быть хорошим кандидатом здесь, и в более общем случае, когда вам нужен многомерный массив. Он обрабатывает все странности, обычно связанные с необработанными массивами C ++, без ущерба для производительности.

Answer 3

В качестве альтернативы, если у вас большая сетка, которая в основном пуста, вы можете использовать std :: map с ключом std :: pair. Вы бы использовали этот подход, только если вас больше беспокоит память, чем время , необходимое для доступа к элементам. Поскольку память будет линейной по количеству непустых ячеек, O (n) и доступ будет O (log n), где при использовании матрицы будет O (mp) в памяти (где m и p - ваши размеры матрицы) и O (1) для доступа.