алгоритм для поиска перекрытий

Question

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

Вот структура корабля:

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 

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

(Battleship?)

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

O (n * длина) время, O (N^2) место.

Answer 5

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

Так преобразовать этот

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 & су, чтобы получить 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 6

Один из способов представления направления - это единичный вектор. Это может быть 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 7

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