c - 寻找重叠的算法

Question

基本上，我有一些 Ship 类型的结构，它们将放置在宽度和高度可变的板上。有关船只的信息是从文件中读取的，我只需要知道确保没有船只重叠的最佳方法。

这是 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

您可以保留整个网格的 bool 数组，最初初始化为“false”。对于每艘船，对于船覆盖的每个位置，检查该位置是否为“假”。如果是，将其设置为“真”。如果没有，那么其他船只就在该位置。

这个算法在所有船只的总面积上是线性的，但是也需要额外的空间与板上位置的数量成正比。