找到一个有效的算法，矩阵运算

对于一个矩阵，我们定义的操作，当我们增加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

2012-09-11 Rannnn

如果我打第一个或最后一个列/行，会发生什么：包装或切割？ –

@EugenRieck它削减 – Rannnn

你的例子是不可能的：1/1/1/1不能从零矩阵创建... –

线性代数？

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

Ñ变量和方程式。解决。通过高斯方法可能存在其他更快的方法。

此外，矩阵是特殊的，因此可能会使它更快。

2012-09-11 02:57:34 Simple

一种使用更多问题结构的方法是使用2-d FFT和卷积定理 - 你拥有的是一个未知矩阵和一个正方形中9 1的模式的卷积。可能有获得非整数的答案的问题，但如果推来推，你可以使用分支和绑定。 – mcdowella

我发现了一些事情（对于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-11 06:22:53 k53sc

错误：3x3矩阵'0 1 0/1 1 1/0 1 0'是可到达的（对中心元素只进行一次操作），但所有元素的总和不能被3整除。 – jrouquie

此外， 2x2矩阵'2 4/4 2'是可到达的（触摸两个对角两次），但是没有相邻元素的差异≤1。 – jrouquie

@jrouquie：“谢谢减号”，我应该提到2x2个案例。提供一个2x2的测试用例，其中总和不能被3整除，并且仍然可以缩小矩阵，“相邻元素差异≤1”是错误的。 – k53sc

回答