오버랩을 찾는 알고리즘

Question

기본적으로 나는 가변 너비와 높이를 가질 수있는 보드에 갈 유형의 구조체가 있습니다. 우주선에 대한 정보는 파일에서 읽혀 지므로 우주선이 겹치지 않도록 최선의 방법을 알아야합니다. 또한

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"로 초기화 된 전체 표의 부울 배열을 유지할 수 있습니다. 각 배에 대해 배가 덮는 각 위치에 대해 그 위치가 "거짓"인지 확인하십시오. 이 값이 0이면 을 "참"으로 설정하십시오. 그렇지 않다면, 다른 배가 그 위치에 있습니다.

이 알고리즘은 모든 선박의 전체 면적에서 선형이지만 보드의 위치 수에 비례하여 추가 공간 인 이 필요합니다.

Answer 2

배송량이 많은 경우가 아니면 단순한 무차별 대입 알고리즘을 사용하면됩니다.이 알고리즘은 두 개의 중첩 루프 (예 : O (n^2))가됩니다.

Answer 3

각 비트가 해당 타일을 점유하는 배가 있는지 여부를 나타내는 보드의 비트 맵을 유지하십시오. 각 선박에 대해 보드에서 차지하는 타일을 표시하고 동일한 비트를 두 번 마크하면 체크 아웃하십시오.

Answer 4

은 (전함?)

하나가 존재할 때 선박의 ID를 포함하는 2 차원 배열 ("기판")를 확인. 따라서 우주선을 추가 할 때 공간이 남아 있는지 여부를 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 

(N, S, E를 얻을 제외 CX에게 & CY를 허용 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

방향을 나타내는 한 가지 방법은 단위 벡터입니다. 이 정수는 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로 초기화 된 부울 값의 2 차원 배열을 만듭니다. 그런 다음 각 선박에 대해 배열에서 해당 항목을 찾은 다음 이미 해당되는 경우 중복됩니다. 그렇지 않으면 해당 항목을 true로 설정하십시오. 모든 함선을 배치했지만 이미 진입 한 항목이 없으면 중복이 없습니다.