Gridflip, 没想出多项式时间的解法来：

Facebook | Programming Puzzles

我的思路是：如果有一系列的flip_col() and flip_row()可以产生满足题设的矩阵，则由于相邻的flip_col()和flip_row()可以相互交换而不影响最终结果，可以把这一系列的flip_col() and flip_row()整理为一系列的flip_row()跟着一系列的flip_col()操作。这样前面的flip_row()操作可以将源矩阵转化为2^m个不同矩阵（每一行可以flip或者不flip，共m行），这2^m个矩阵的每列元素如果为负，则需要flip_col，如果为正则不需要进行flip_col。然后检查最终的结果矩阵是不是符合题设，将所有的可行矩阵计算出来后取S最小的那个。时间复杂度是O(2^m*m*n)。
暂时只想到这么多，ajoo把你的非多项式时间的解法也讲讲看。

差不多也是这样吧。可以先判断行多还是列多，先从少的那个轴开始走，会快一些。不过你忽略了和为0的情况，这时候可能要翻和不翻都试一遍的。所以似乎最坏情况是2^(m+n)

觉得应该有更聪明的算法的，否则他们给你一个30＊30的数据，不就歇了？

这题看着象 NPC 的，可能没有多项式算法。想了一阵，也没有什么直观的方法，可以考虑转成线性规划去做。