请大家给点这个题的解题思路!
------------------------------------
标题:剪格子 如图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.jpgp2.jpg2013 蓝桥杯 第10题Java
------------------------------------
标题:剪格子 如图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.jpgp2.jpg2013 蓝桥杯 第10题Java
原来你们是一路的啊
希望你能出一些具体实现API类。
当你试图访问的格子碰到了一条边,并且在与此边平行的方向上这个格子没有邻居,那这个格子就不能被包含在解中,因为它会让这块布变成3块而不是2块。用这个条件取代找出解集后验证的步骤,效率更高。这个不需要API,简单的二维数组就能搞定。在不需要用API的时候强制使用API,效率只会更低。你想,API其实也只是包装了一些基本的东西而已,怎么可能比你直接用基本的东西快?(当然,有个别东西是做了JVM级别的优化的,比如Sytem.arraycopy,这个就要多研究啦)There is no magic in Java API
-------------------------------------------
2013年 蓝桥杯 初赛 Java高职高专组 第10题
1)
从左上角出发查找,如果存在图2的数据,则在查找过程中可能出现回溯( 虚线箭头的部分)
2)
回溯疑难问题
从左上角出发,向四方发散!图3这种情况不可能出现(因为被分隔成了3个区域)
(注意虚线箭头的部分,是回溯部分)
而这种情况是可能的,见图4,所以可能是向四方发散(可以向左,向上)还有可能是这种情况,见图5
解题思路:
从左上角格子出发
1. 排除和为奇数的情况
2. 边界问题
边界条件:跟随路径查找到区域的边界,如果与该格子平行的行或列上,没有相邻的格子,则不符合条件,排除。
3. 查找路径问题
1)根据值判断(假定n为总和)
<1> 排除相加和>n/2的情况
<2>如果是= n/2则查找完毕
<3>如果是<n/2 则继续查找
2)根据查找记录判断:判断该格子是否已经查找过,
<1> 若存储过该格子的查找记录,排除
<2> 若没有存储过,继续沿该路径查找
3)向四方分散,分治问题与递归的实现
4. 存值问题
<1>存储已找到的格子
<2>存储已找到格子的值的总和