algorithm - 尽可能将学生安排在尽量减少作弊的位置

Question

给定一个大小为 m * n 的矩阵，将 k 个学生按这样的方式放置，使得考试作弊的可能性最小。

我的方法:考虑一个 m * n 矩阵，将第一个学生放在 X 处，(X= 给定矩阵中的任何单元格)。对于下一个学生做一个 BFS，对于每个空单元格，计算它的距离 (R)。对于 R，我们可以从值 t=max(m, n) 开始，在 BFS 中遇到同一级别的每个下一个单元格时，我们添加 t 级别。如果 R 最小，则存储此单元格直到现在。最后将下一个学生放入具有最小 R 值的单元格中。对所有学生 (k) 重复此操作。

优化:如果我们到达的单元格的 R 大于我们之前的值，则忽略它。

我们如何优化它？
有没有更好的算法来做到这一点？
我的起始单元格 X 与最终答案有关吗？

例如，如果它是 5x5 垫子，我将第一个学生放在 0x0 处，或者如果我从 2x2 开始，对于广义 k 哪个更好？ (显然对于 k=2，0x0 会更好!)

编辑这里最小化作弊意味着为所有学生计算的 Rs 总和应该尽可能小。

Answer 1

所以基本上你想在一个 m 乘 n 的平面中打包 k 个圆？你为什么不简单地使用六角填料？也许检查https://en.wikipedia.org/wiki/Circle_packing及相关文章。