找到重叠的算法

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".如果没有,那么其他一些船就在这个位置上.

该算法在所有船舶的总面积上是线性的,但也需要与板上位置数量成比例的额外空间.