这是一个面试问题:
对于矩阵,我们定义一个操作,当我们将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
algorithm ×1