这是一道面试题:
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
最佳答案
线性代数?
Cell i,j is touched x<sub>ij</sub> times.
n2 个变量和方程。解决。 O(n^6)
通过高斯方法,可能存在其他更快的方法。
此外,matrix 很特殊,因此可能会使其更快。
关于algorithm - 找到矩阵运算的有效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12361634/