蓝桥杯 - [2013年第四届真题]剪格子(DFS)
发布日期:2021-07-01 00:18:33
浏览次数:3
分类:技术文章
本文共 1492 字,大约阅读时间需要 4 分钟。
题目链接:
时间限制:1.0s 内存限制:256.0MB问题描述
如下图所示,3 x 3 的格子中填写了一些整数。
+--*--+--+ |10* 1|52| +--****--+ |20|30* 1| *******--+ | 1| 2| 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
解题思路
直接用DFS从左上角搜索一下就行了,注意如果总和是奇数,肯定不能。
#includeusing namespace std;const int inf = 0x3f3f3f3f;int n, m, sum, min_, a[15][15], vis[15][15];int arr[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};void DFS(int x, int y, int s, int t) { if (s > sum || t >= min_) return ; if (!(s - sum)) { min_ = min(min_, t); return ; } for (int i = 0; i < 4; i++) { int tx = x + arr[i][0]; int ty = y + arr[i][1]; if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty]) { vis[tx][ty] = 1; DFS(tx, ty, s + a[tx][ty], t + 1); vis[tx][ty] = 0; } }}int main() { sum = 0; scanf("%d%d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); sum += a[i][j]; } } if (sum & 1) { printf("0\n"); return 0; } sum >>= 1; min_ = inf; vis[0][0] = 1; DFS(0, 0, a[0][0], 1); if (min_ < inf) printf("%d\n", min_); else printf("0\n"); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/90417258 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月30日 06时56分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
maven打包可运行的JAR
2019-05-02
linux sar 命令详解
2019-05-02
LINUX 使用管道实现无需落地文件GZIP压缩
2019-05-02
pure-ftp 启用虚拟账户的问题
2019-05-02
ipvsadm 安装配置
2019-05-02
linux下nc的使用
2019-05-02
sed学习---字符替换
2019-05-02
Linux shell脚本的字符串截取
2019-05-02
linux和windows下mysql密码怎样清空!
2019-05-02
mysql logs-slave-updates (A -> B -> C)
2019-05-02
关于Java中split方法对空字符串处理问题
2019-05-02
Find–atime –ctime –mtime的用法与区别总结
2019-05-02
详解MySQL中EXPLAIN解释命令
2019-05-02
Python 获得命令行参数的方法
2019-05-02
python对文件进行读写操作
2019-05-02
轻松搞定linux端口转发
2019-05-02
python数组的使用
2019-05-02
常见的几种python字符串方法总结
2019-05-02
shell 常用正则表达式
2019-05-02