c++ - 网格中的有效方法

Question

问题：我们必须用集合 S 中的字符填充大小为 m*n 的 2D 网格，以使生成的网格中不同子矩阵的数量接近给定数量 k。
这个问题来自http://www.codechef.com/JULY14/problems/GERALD09

限制：
1<=n,m<16
1<=k <=m*n*m*n
|S|=4
时间限制=0.1 秒

假设：如果两个子矩阵的维度不同或至少有一对在其对应位置的字符不匹配，则它们是不同的。

我的方法：我们可以从随机网格和循环开始，同时找到可接受的解决方案，并且在每次迭代中，我们可以根据当前状态增加/减少随机性（但我们可以停留在局部最优状态）。

但问题是我不知道计算子网格中不同子矩阵数量的有效方法。我尝试用散列法进行计数，这非常快（ O(n ² m ² )*生成/搜索的成本子网格的哈希值）。但是由于哈希值的冲突，这种方法并没有给出准确的答案，即使在使用@Vaughn Cato 的评论更正它之后，我也可以进行 15-25 次迭代以获得最佳状态查找，但这还不够。

最近，我了解到模拟退火可以用来解决这类问题。
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
我正在寻找任何有效的方法来解决这个优化问题。

提前致谢。

Answer 1

我认为他们会在某个时候发表社论，但对于这个特定问题，这里有一个可能的想法：

我在本地生成了所有可能数量的特定子矩阵n和m。因为n=m=3我只是11出于81可能性。因为n=3,m=4我只得到19了可能的144值。更重要的是，当我生成这些值时，我19在一开始就获得了所有可能的选项——在263000矩阵不可能之后16M我已经有了它们。（我按字典顺序生成）

因此，我认为，一种可能的解决方案可能是预先计算尽可能多的不同值K，可以为给定的n和实现m，保存随机生成器的种子或以其他方式保存O(1)每个三元组的字符n-m-k，以及特定的测试用例只检查两个相邻的值 - 首先k大于和小于给定的值。

更重要的是，由于可能K值的数量并不多，因此可以通过其他方式生成它们：给定Kfor nxmtable 的所有可能值以及适当的表，我们只能回溯下一行中的值，并且尝试获得具有所有不同值的所有可能矩阵Kfor nx(m+1)。