java - 如何有效地在网格上选取一条穿过某些点的线

Question

假设我有一个 30 x 30 的网格，上面有四个代表妖精的 (x,y) 坐标。

我想放置一条 1 x 10 宽和长的线，穿过尽可能多的妖精。

获得答案的有效方法是什么？

测试源到目标行的每种组合的成本太高，因此我需要一些能够给我一个不错的答案的东西，而不必是完美的。

Answer 1

只是添加一些有关 @GilbertLeBlanc 答案的详细信息:

“选取四个妖精中的任意两个，并用线将它们连接起来。”

如果您随机选择它们:

1. 如果没有三个在同一行，那么您就有最佳答案；
2. 如果所有四个都在同一行，那么您就有最佳答案；
3. 如果三个对齐而一个未对齐，则获得最佳答案的概率为 1/2。

总而言之，已经相当不错了。