5

这是一道面试题：

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

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

我目前能想到的是使用回溯来尝试所有可能的组合，但这绝对不是有效的。这个问题有点像关灯游戏，但这里不是 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
4

2 回答 2

1

线性代数？

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

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

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

于 2012-09-11T02:57:34.887 回答
0

我发现了一些东西（对于 2x2 矩阵），想先分享它们
- 矩阵中所有元素的总和应该被 3 整除（那么只有它是可能的）。
-我们必须以允许的操作步骤的形式表达给定的矩阵

3 3  -> 2* 1 1    +    1* 1 1
1 2        0 1            1 0

在某些情况下这是无法做到的，例如

5 3  ->2* 1 0  +   2* 1 1     = 4 2
2 4       1 1         0 1       2 4

5 3   -   4 2     = 1 1 (this is not allowed operation)
2 4       2 4       0 0
于 2012-09-11T06:22:53.073 回答