recursion - 减少学生作弊

Question

给定一个大小为 m * n 的矩阵，以这样的方式安排 k 个学生，以使考试中的作弊最小化

我的想法：

使用蛮力方法，创建所有可能的学生展示位置组合，并返回作弊分数最低的组合，而作弊分数定义为每两个学生之间的曼哈顿距离之和。

这种方法的时间和空间复杂度非常糟糕，有更好的解决方案吗？

Answer 1

int 2d array to store  4 values for every variable 
0:no neighbor
1:diagnol neighbor
2:horizontol or vertical neighbor
4:filled seat
now everytime create randomindex for row and column and first priority given to no neighbor until this expires
Then priority given to diagnol until expires
at last horizontol or vertical neighbor

repeat above steps till count=k

Answer 2

1）几何直觉——也许试着把前4个放在正方形的外角，然后从那里螺旋向内？

这大约适用于“毕达哥拉斯距离”，也许您可​​以适应相当于向内螺旋路径的“曼哈顿距离”，然后沿着该路径线性放置学生。

---

2）或者，您可以将学生按顺序排列在下一个作弊最低标准；然后，一旦所有学生都被放置，扰动位置以达到“整体最小值”。

我可能最喜欢 2) 作为一种方法。