当前位置: 首页 > news >正文

洛谷P8601[蓝桥杯][2013年第四届真题]剪格子

题目描述

如图 11 所示,3×3 的格子中填写了一些整数。

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

本题的要求就是请你编程判定:对给定的 m×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

说明/提示

第二个用例中:

时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

思路:利用搜索遍历每一种解决方案,把每种解决方案中格子的个数记录下来,然后输出最少格子数

#include<iostream>
using namespace std;
int g[11][11];
int vis[11][11];
int n, m, num[10010], sum, s, k;
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,1,0,-1 };
void dfs(int x, int y)
{if (s == sum / 2){for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (vis[i][j] == 1) num[k]++;}}k++;return;}for (int i = 0; i < 4; i++){int dx = x + xx[i];int dy = y + yy[i];if (dx>=1 && dx<=n && dy>=1 && dy<=m && vis[dx][dy]==0 ){vis[dx][dy] = 1;s += g[dx][dy];dfs(dx, dy);s -= g[dx][dy]; //回溯vis[dx][dy] = 0;}}
}
int main()
{cin >> m >> n;int i, j;for (i = 1; i <= n; i++){for (j = 1; j <= m; j++){cin >> g[i][j];sum += g[i][j];}}vis[1][1] = 1;s += g[1][1];dfs(1, 1);int minn = num[0];for (i = 0; i < k; i++){minn = min(minn, num[i]);}cout << minn << endl;return 0;
}

这串代码在洛谷中只能跑过3个测试案例,暂时还没有找到更好的解决方法,呜呜~~

相关文章:

洛谷P8601[蓝桥杯][2013年第四届真题]剪格子

题目描述如图 11 所示&#xff0c;33 的格子中填写了一些整数。我们沿着图中的红色线剪开&#xff0c;得到两个部分&#xff0c;每个部分的数字和都是 60。本题的要求就是请你编程判定&#xff1a;对给定的 mn 的格子中的整数&#xff0c;是否可以分割为两个部分&#xff0c;使…...

配置alias实现快速生成.gitignore文件

git工具&#xff1a;版本控制开发工具。 cscope工具&#xff1a;用于浏览C源码的工具&#xff0c;类似于ctags。在代码根目录下执行cscope -Rbq&#xff0c;然后产生三个索引文件&#xff08;cscope.out、cscope.in.out和cscope.po.out三个文件&#xff09;。 在Linux下使用vi…...

MySQL数据库调优————GROUP BY及DISTINCT优化

GROUP BY 三种处理GROUP BY的方式 松散索引扫描&#xff08;Loose Index Scan&#xff09;紧凑索引扫描&#xff08;Tight Index Scan&#xff09;临时表&#xff08;Temporary table&#xff09; 三种方式的性能一次递减 松散索引扫描 无需扫描满足条件的所有索引键即可返…...

LRU缓存算法

双向链表哈希表&#xff08;非线程安全&#xff09; https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/ /*** LRU算法: 哈希表双向链表实现* 1. 双向链表按照被使用的顺序来存储, 靠近头部的节点是最近使用的, 靠近尾部的节…...

@Configuration注解

Configuration注解介绍 Configuration注解&#xff0c;用于标注一个类是一个spring的配置类&#xff08;同时&#xff0c;也是一个bean&#xff09;&#xff0c;配置类中可以使用ComponentScan、Import、ImportResource 和 Bean等注解的方式定义beanDefinition。 Target(Elem…...

基于springboot+vue的食疗系统

基于springbootvue的食疗系统 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&…...

sklearn学习-朴素贝叶斯

文章目录一、概述1、真正的概率分类器2、sklearn中的朴素贝叶斯二、不同分布下的贝叶斯1、高斯朴素贝叶斯GaussianNB2、探索贝叶斯&#xff1a;高斯朴素贝叶斯擅长的数据集3、探索贝叶斯&#xff1a;高斯朴素贝叶斯的拟合效果与运算速度总结一、概述 1、真正的概率分类器 算法…...

分享112个HTML艺术时尚模板,总有一款适合您

分享112个HTML艺术时尚模板&#xff0c;总有一款适合您 112个HTML艺术时尚模板下载链接&#xff1a;https://pan.baidu.com/s/1D3-mfPOud-f3vy9yLl-bmw?pwdfph2 提取码&#xff1a;fph2 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 时尚平面模特网站模板 潮…...

用GDB远程调试运行于QEMU的程序

1. 前言 限于作者能力水平&#xff0c;本文可能存在谬误&#xff0c;因此而给读者带来的损失&#xff0c;作者不做任何承诺。 2. 测试环境 本文使用 Ubuntu 16.04.4 LTS QEMU 环境进行调试。 3. 用 GDB 调试 QEMU 内程序 3.1 编写用来调试的程序 我们用 ARM32 来进行调试…...

20 堆排序

文章目录1 堆排序的概念2 堆排序基本思想3 堆排序步骤图解说明4 堆排序的代码实现1 堆排序的概念 1) 堆排序是利用堆这种数据结构而设计的一种排序算法&#xff0c;堆排序是一种选择排序&#xff0c;它的最坏&#xff0c;最好&#xff0c;平均时间复杂度均为 O(nlogn)&#xf…...

2023最新文件快递柜系统网站源码 | 匿名口令分享 | 临时文件分享

内容目录一、详细介绍二、效果展示1.部分代码2.效果图展示三、学习资料下载一、详细介绍 2023最新文件快递柜系统网站源码 | 匿名口令分享 | 临时文件分享 很多时候&#xff0c;我们都想将一些文件或文本传送给别人&#xff0c;或者跨端传递一些信息&#xff0c;但是我们又不…...

分片策略(二)

分片策略 基本概念 分片键 用于分片的字段&#xff0c;是将数据库或表拆分的字段&#xff0c;比如&#xff0c;我可以使用user_id作为分片键将用户数据分到不同的表中&#xff0c;这里的user_id就是分片键&#xff0c;除了这种单字段分片&#xff0c;ShardingSphere还支持多…...

Qt之调色板类QPalette的使用

文章目录QPalette调色板类前言代码知识点讲解QPalette调色板类 前言 Qt提供的调色板类QPalette专门用于管理部件的外观显示&#xff0c;相当于部件或对话框的调色板&#xff0c;管理他们所有的颜色信息。每个部件都包含一个QPalette对象&#xff0c;在显示时&#xff0c;按照…...

Kotlin 32. Kotlin 多语言支持

Kotlin 多语言支持 对于 Kotlin 来说&#xff0c;当我们新建一个项目时&#xff0c;会默认在 values/ 文件夹下&#xff0c;生成一个 strings.xml 文件。比如说&#xff0c; <resources><string name"app_name">exampleNewProject</string> <…...

【Flutter入门到进阶】Dart进阶篇---DartVM单线程设计原理

1 虚拟机的指令执行设计 1.1 虚拟机的分类 基于栈的虚拟机&#xff0c;比如JVM虚拟机 基于寄存器的虚拟机&#xff0c;比如Dalvik虚拟机 1.2 虚拟机的概念 首先问一个基本的问题&#xff0c;作为一个虚拟机&#xff0c;它最基本的要实现哪些功能&#xff1f; 他应该能够模拟…...

Dem和NvM(NVRAM Manager)的交集

NVRAM&#xff08;NvM&#xff09;提供了在NVRAM中存储数据Block的机制。 NVRAM Block&#xff08;最大大小取决于配置&#xff09;被分配给Dem&#xff0c;并由Dem实现事件状态信息和相关数据的永久存储&#xff08;例如通电复位&#xff09;。 ECU 状态管理器&#xff08;Ec…...

AI神经网络CNN/RNN/DNN/SNN的区别对比

@版权声明: 本文由 ChatGpt 创作; BiliBili: https://www.bilibili.com/video/BV17D4y1P7pM/?share_source=copy_web&vd_source=6d217e0ff6387a749dc570aba51d36fd 引言 随着人工智能技术的发展,神经网络作为人工智能的核心技术之一,被广泛应用于图像识别、语音识别、…...

【JavaWeb】一文学会JPA

✅✅作者主页&#xff1a;&#x1f517;孙不坚1208的博客 &#x1f525;&#x1f525;精选专栏&#xff1a;&#x1f517;JavaWeb从入门到精通&#xff08;持续更新中&#xff09; &#x1f4cb;&#x1f4cb; 本文摘要&#xff1a;本篇文章主要介绍JPA的概念、注解实现ORM规范…...

【安卓逆向】APK修改与反编译回编译

【安卓逆向】反编译修改APK回编译使用工具流程步骤Apktool相关安装与使用常用命令备查APK签名命令备查实战练习反编译查看修改的地方使用Apktool反编译得到产物文件夹并进行修改回编APK实用场景在日常开发我们可能需要替换某些资源或者修改某些代码&#xff0c;但是我们没有源码…...

【计组笔记04】计算机组成原理之多模块存储器、Cache高速缓存存储器、Cache地址映射

这篇文章,主要介绍计算机组成原理之多模块存储器、Cache高速缓存存储器、Cache地址映射。 目录 一、双口RAM和多模块存储器 1.1、存取周期 1.2、双口RAM 1.3、多模块存储器...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...