algorithm - 找到矩阵运算的有效算法

Question

这是一道面试题:

For a matrix, we define an operation that when we add 1 to one entry, all the surrounding entries (up, down, left, right) will also added by 1. Given a positive matrix, find an algorithm to determine if the matrix can be constructed from zero matrix using such operation.

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

我目前能想到的就是用回溯的方式尝试每一种可能的组合，但是这样效率肯定不高。这个问题有点像 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² 个变量和方程。解决。 O(n^6) 通过高斯方法，可能存在其他更快的方法。

此外，matrix 很特殊，因此可能会使其更快。