алгоритм поиска совпадений

Question

В основном у меня есть некоторые структуры типа Корабль, которые собираются идти на доске, которая может иметь переменную ширину и высоту.Информация о кораблях читается из файла, и мне просто нужно знать, как лучше убедиться, что ни один из кораблей не перекрывается.

Кроме того, что было бы хорошим способом справиться с указаниями.Что-то более чистое, чем использование оператора switch и использование разных условий для каждого направления.

Любая помощь будет принята с благодарностью!

Answer 1

Вы можете оставить логический массив всей сетки, изначально инициализированный как «false». Для каждого корабля, для каждого местоположения, которое охватывает корабль, проверьте, является ли местоположение «ложным». Если это, установите его в «true». Если нет, то другой корабль находится на месте.

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

Answer 2

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

Так что конвертируйте это

int x // x position of first part of ship
int y // y position of first part of ship
char dir // direction of the ship, either 'N','S','E' or 'W'
int length // length of the ship

в это (разрешите отрицательные cx и cy получить N, S, E, W)

int x // x position of first part of ship
int y // y position of first part of ship
int cx // length of the ship in X 
int cy // length of the ship in Y

или это

int left   // x position of Eastern part of the ship
int top    // y position of Northernmost part of ship
int right  // x position of Westernmost part of the ship
int bottom // y position of Southernmost part of ship
bool orientation; // so we can tell East from West or North from South.

Тогда простая функция может определить, пересекаются ли два корабля.

bool DoShipsIntersect(Ship * a, Ship * b)
{
    if ((a->right < b->left) || (b->right < a->left))
       return false;
    if ((a->bottom < b->top) || (b->bottom < a->top))
       return false;
    return true;
}

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

Answer 3

Возможно, вы захотите использовать тип enum для вашего направления. С точки зрения поиска совпадений, создайте двумерный массив логических значений, инициализированный для false для вашей доски. Затем для каждого корабля, найдя соответствующие записи в массиве и, если они уже верны, у вас есть перекрытие. В противном случае установите для этих записей значение true. Если вы разместили все свои корабли и не встретили уже истинного входа, то перекрытия нет.

Answer 4

Одним из способов представления направления является единичный вектор. Это может быть 2 целых числа: dirX и dirY. Например. dirX = 1 для Востока; или dirY = 1 для юга.

Затем вы можете выполнить итерацию по всем позициям, занимаемым кораблем:

int cx = x;
int cy = y;
for(int i = 0; i < length; i++) {
    cx += dirX;
    cy += dirY;
}

Или получите ограничивающий прямоугольник на основе этих значений:

x
y
x + dirX * (length - 1)
y + dirY * (length - 1)

Answer 5

(Battleship?)

Создайте двумерный массив («доска»), который содержит идентификатор корабля, когда он присутствует. Поэтому, когда вы добавляете корабль, вы можете за O (продолжительность) проверить, занято ли пространство или нет.

O (n * length) время, O (N ^ 2) пробел.

Answer 6

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

Answer 7

Если у вас не много кораблей, просто используйте простой алгоритм грубой силы, который будет двумя вложенными циклами, т. Е. O (n ^ 2).