寻找一种高效的矩阵操作算法。

Question

这是一个面试问题：

对于一个矩阵，我们定义这样一个操作：将其中一个元素加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

- Rannnn

---

如果我点击第一列/行或最后一列/行会发生什么：换行还是裁剪？ - Eugen Rieck

你的例子是不可能的：1/1/1/1 无法从零矩阵中创建... - Eugen Rieck

@EugenRieck 已编辑，现在这里有一个可能的解决方案。尝试反向解决它。 - Rannnn

似乎是一个简单的动态规划挑战。 - Stephen Nutt

Answer 1

线性代数？

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

有n²个变量和方程式。解决。高斯方法的时间复杂度为O(n^6)，可能存在其他更快的方法。

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

- Simple

---

一种更多地利用问题结构的方法是使用二维FFT和卷积定理 - 你所拥有的是一个未知矩阵和一个方形中有9个1的模式的卷积。可能会出现获取非整数答案的问题，但如果必要，可以使用分支限界法来解决。 - mcdowella

Answer 2

我找到了一些关于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

- 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