一路考算法的题

一道考算法的题
标题：剪格子

    如图p1.jpg所示，3 x 3 的格子中填写了一些整数。

    我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。

    本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
    如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。   
    如果无法分割，则输出 0

程序输入输出格式要求：
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000
程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。 算法
[解决办法]
可以使用树的遍历。
下面的结点是孩子，右边的结点是兄弟。
[解决办法]
还有一种方法，使用扩散
[解决办法]

引用:

楼上的说法我觉得有点问题。。能够符合条件的不一定是几个最大的数组合, 也可能是几个大的数配级个小的数

所以我特意写了递归，而查找的顺序是＂从大的格子找起＂，而不是只找大的格子。其目的是更早找出较优解，来终止更多错误路径
[解决办法]

引用:

楼上怎么写的 求贴代码

最近比较忙，比较忙，比较忙。。。不过大概步骤就是。。具体代码你就自己琢磨吧，不能懒啊。。

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
  }
}

查看更多 下一篇