找到一种有效的矩阵运算算法

Question

这是一个面试问题:

对于矩阵,我们定义一个操作,当我们将1添加到一个条目时,所有周围的条目(向上,向下,向左,向右)也将加1.给定正矩阵,找到一个算法来确定矩阵是否可以使用这种操作从零矩阵构造.

什么是解决问题的有效算法？

我现在能想到的是使用回溯来尝试所有可能的组合,但这绝对不是有效的.问题有点像Lights Off游戏,但这里不是0/1,这使得更复杂.

谢谢.

编辑:

例如:

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3
1 2                         0 0    1 0    1 1    1 2

Answer 1

线性代数？

Cell i,j is touched x<sub>ij</sub> times.

n ^{2 个}变量和方程。解决。O(n^6)通过高斯方法，可能存在其他更快的方法。

另外，矩阵很特殊，因此也许可以使其更快。