当前位置: 代码迷 >> J2SE >> 一路考算法的题
  详细解决方案

一路考算法的题

热度:87   发布时间:2016-04-23 22:10:41.0
一道考算法的题
标题:剪格子

    如图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
  }
}
  相关解决方案