【100题】第四十五题 雅虎面试两道题（矩阵判断、数组划分）

一，对于一个整数对于一个整数矩阵矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

分析：对任意一个位置,他的值不大于周围(上下左右)4个临格的数值的和，如果大于则该矩阵不能由全零矩阵得到

解法一：可能是我能想到的最复杂的方法

1）将二维数组根据行优先原则，变为一维数组。

2）然后对一维数组进行排序，取不为零的值，将元素对应的值拆分成对应个数该元素，然后全排列。这样得到所有可能的矩阵元素递减策略。例如A[0][0] = 3 则对应 A[0] 拆分成3个A[0]

3）对上述排列逐一判断

1>如果相邻元素在二维数组中不“相邻”则排除

2>如果同一个元素相邻则排除

3>遍历到某个排列时，正好遍历完则返回正确

如果遍历完整个全排列，也没有得到正确结果，则说明不能由全零矩阵得到整形 矩阵 解法二：优化解法一

1）先扫描整个二维数组，如果某个元素值大于其周围元素值和，则返回错误

2）然后利用动态规划，递归的思路。

自己写的递归算法，不知有无错误。敬请斧正！！！谢谢！！！