蓝桥杯C／C++省赛：剪格子-腾讯云开发者社区-腾讯云

admin 感悟评价 2024-04-12 59浏览 0

　　题目描述

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

　　我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

蓝桥杯C／C++省赛：剪格子-腾讯云开发者社区-腾讯云

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。如果无法分割，则输出 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

蓝桥杯C／C++省赛：剪格子-腾讯云开发者社区-腾讯云

　　资源约定：峰值内存消耗 < 64M CPU消耗 < 5000ms思路分析

　　问题是可以变成路径问题，如果有解，那么找出一条从左上角开始的一条路径，这条路径的带权长度为总路径长度的一半。

　　采用深度优先遍历搜索，递归求解。

　　递归有两个问题需要解决，一个是什么时候return回去，一个是往哪里递归。

　　递归结束的条件一般是遇到边界返回，或者是找到解，这里存在最优解的情况，所以还需要记录每次解，将其和当前最优解进行比较。

蓝桥杯C／C++省赛：剪格子-腾讯云开发者社区-腾讯云

　　方向是往上下左右递归，这里需要记得标记为已访问之后，回溯的时候需要取消标记，重新标记为未访问。然后距离和计数都退回上一步的状态。AC代码

转载请注明：pg电子·(中国)官方网站 » 感悟评价 » 蓝桥杯C／C++省赛：剪格子-腾讯云开发者社区-腾讯云

版权声明

本文仅代表作者观点，不代表B5编程立场。
本文系作者授权发表，未经许可，不得转载。

发表评论