当前位置: 代码迷 >> J2SE >> 求答题思路:2013蓝桥杯Java高职高专组第10题
  详细解决方案

求答题思路:2013蓝桥杯Java高职高专组第10题

热度:97   发布时间:2016-04-23 22:05:53.0
求解题思路:2013蓝桥杯Java高职高专组第10题
请大家给点这个题的解题思路!
------------------------------------
标题:剪格子

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

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

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

程序输入输出格式要求:
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000
程序输出:在所有解中,包含左上角的分割区可能包含的最小的格子数目。


例如:
用户输入:
3 3
10 1 52
20 30 1
1 2 3

则程序输出:
3

再例如:
用户输入:
4 3
1 1 1 1
1 30 80 2
1 1 1 100

则程序输出:
10

(参见p2.jpg)
图片参考:
p1.jpg

p2.jpg

2013?蓝桥杯??第10题 Java

------解决方案--------------------
想到一个方法不知道行不行,就是那些格子的数用一个数组来存放,然后计算所有格子里的数的总值,拿第一张图来说,总值就是120,然后总值除2,得到一半的分数,然后遍历数组,看那几个数组元素相加会等于那一半的分数
------解决方案--------------------
类似图的遍历,从一个顶点出发,经过一些顶点后又回到这个顶点,把所有的可能遍历一遍。顶点之间是否可达有条件,遍历完成后,算出你此次遍历的顶点包围的数字和,与剩余数字和否相等,在所有可能中找到包含左上角的数目最小框的那一条路线就可以了
------解决方案--------------------
我的代码有一步验证的过程,不过我现在有更好的方法:
当你试图访问的格子碰到了一条边,并且在与此边平行的方向上这个格子没有邻居,那这个格子就不能被包含在解中,因为它会让这块布变成3块而不是2块。用这个条件取代找出解集后验证的步骤,效率更高。

这个不需要API,简单的二维数组就能搞定。在不需要用API的时候强制使用API,效率只会更低。你想,API其实也只是包装了一些基本的东西而已,怎么可能比你直接用基本的东西快?(当然,有个别东西是做了JVM级别的优化的,比如Sytem.arraycopy,这个就要多研究啦)

There is no magic in Java API
  相关解决方案