一道考算法的题

Question

算法

Answer 1

有个想法。。不过没实践过。。首先把全部数的和算出来当做一个变量maxCount，如果是奇数直接返回false
然后new一个栈遍历整个M * N的数据 ，再定义一个变量statckCount，每次push一个数据进来就加上去。如果stackCount == maxCount/2,就可以得到解了。

Answer 2

先计算出二维数组的和，奇数false，偶数的话，算出和的一半，然后用和减去要循环判断的第一项，跟数组中最大的数作比较，得到最小循环次数，跟数组中最小的数做比较，得到最大循环次数，你看这样如何？

Answer 3

在旅行中，无法写代码测试，给个思路，抛砖引玉类似一个A*搜索算法，搜索起点在左上角，找到一条格子最少的路，和为总数一半。
每一步都从数字最大的格子找起（递归）
当找到一条路时，再判断这条路是否能剪切。如果能，则记下格子的数量为目前最优解
当搜索其他路径时，如果格子数量超过最优解，则终止该路径而转向其他路径判断解是否可剪切，选一个路径之外的格子，做一次遍历，遍历到的格子总数与当前路径格子数相加，看是否为m*n选路径外的格子，我就不说了有很多种方法。。

Answer 4

最近比较忙，比较忙，比较忙不过大概步骤就是。。具体代码你就自己琢磨吧，不能懒啊。。
private int currentMinSteps = Integer.MAX_INT;
// this is the recursion I mentioned
void find (Tile currentTile, int currentSteps) {
  Tile tiles[] = findTilesAround(currentTile);
  sortTilesByItsNumber(tiles);
  for (Tile tile: tiles) {
   if (hasVisited(tile)) continue;
   if (calculateCurrentTotal(tile) == halfTotal){
     if (isSolutionCuttable()) // the step I mentioned to test if the solution can be cut by just once
        currentMinSteps = currentMinSteps < currentSteps ? currentMinSteps : currentSteps;
     continue;
   }
   else if (currentSteps >= currentMinSteps) continue; // this is where time gets saved
   else
    find (tile, currentSteps + 1); // the recursive step, which will find all solutions
  }
}

Answer 5

回复20楼：
贪心+回溯 实现。
http://blog.csdn.net/jopus/article/details/19082697