当前位置: 首页 > 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、多模块存储器...

QueryExcel:5分钟搞定上百个Excel文件的批量查询终极指南

QueryExcel&#xff1a;5分钟搞定上百个Excel文件的批量查询终极指南 【免费下载链接】QueryExcel 多Excel文件内容查询工具。 项目地址: https://gitcode.com/gh_mirrors/qu/QueryExcel 你是否曾面对数十甚至上百个Excel文件&#xff0c;需要从中查找特定信息&#xff…...

Biliup录制工具终极指南:如何合法合规地进行视频录制与上传

Biliup录制工具终极指南&#xff1a;如何合法合规地进行视频录制与上传 【免费下载链接】biliup 自动直播录制、投稿、twitch、ytb频道搬运工具。命令行投稿(B站)和视频下载工具&#xff0c;提供多种登录方式&#xff0c;支持多p。 项目地址: https://gitcode.com/gh_mirrors…...

告别Calibre中文路径乱码:3步实现完美文件名保护的终极解决方案

告别Calibre中文路径乱码&#xff1a;3步实现完美文件名保护的终极解决方案 【免费下载链接】calibre-do-not-translate-my-path Switch my calibre library from ascii path to plain Unicode path. 将我的书库从拼音目录切换至非纯英文&#xff08;中文&#xff09;命名 项…...

告别野火原子,用江科大STM32F103模板+Keil5,30分钟搞定RT-Thread Nano 3.0.3移植

江科大STM32F103模板Keil5快速移植RT-Thread Nano 3.0.3实战指南 如果你正在使用江科大的STM32F103教学模板&#xff0c;想要快速实现RT-Thread Nano 3.0.3的移植&#xff0c;这篇文章将为你提供一个30分钟完成的详细方案。相比野火、正点原子等开发板&#xff0c;江科大模板在…...

注意力机制改进效果对比实验与分析

深夜调参现场&#xff1a;上周三凌晨两点&#xff0c;盯着验证集mAP曲线在0.735附近反复横跳&#xff0c;已经卡了三天。 backbone换成CSPDarknet53&#xff0c;Neck加了BiFPN&#xff0c;数据增强全上了&#xff0c;可小目标检测的AP_s死活上不去。同事扔来一篇论文&#xff1…...

3步解锁百度网盘SVIP特权:macOS用户必备的高速下载解决方案

3步解锁百度网盘SVIP特权&#xff1a;macOS用户必备的高速下载解决方案 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS 还在为百度网盘Mac客户端的龟速…...

Bottlerocket容器健康检查终极指南:自定义探针与系统指标深度集成

Bottlerocket容器健康检查终极指南&#xff1a;自定义探针与系统指标深度集成 【免费下载链接】bottlerocket An operating system designed for hosting containers 项目地址: https://gitcode.com/gh_mirrors/bo/bottlerocket Bottlerocket是一款专为容器化工作负载设…...

QueryExcel:解锁3大核心功能的多Excel文件极速查询指南

QueryExcel&#xff1a;解锁3大核心功能的多Excel文件极速查询指南 【免费下载链接】QueryExcel 多Excel文件内容查询工具。 项目地址: https://gitcode.com/gh_mirrors/qu/QueryExcel 直击痛点&#xff1a;数据查询的效率困境 场景一&#xff1a;财务报表核对 月底需从…...

华为云CCE内网部署Nacos集群实战:不用Helm,纯页面操作搞定镜像上传与配置

华为云CCE内网部署Nacos集群实战&#xff1a;纯控制台操作指南 在企业级容器化部署场景中&#xff0c;内网环境下的服务部署往往面临特殊挑战。当安全合规要求严格限制外网访问时&#xff0c;传统依赖公网镜像仓库和Helm工具的部署方案便不再适用。本文将详细介绍如何在华为云…...

Phi-4-mini-reasoning加速深度学习:卷积神经网络(CNN)模型设计与调优实战

Phi-4-mini-reasoning加速深度学习&#xff1a;卷积神经网络&#xff08;CNN&#xff09;模型设计与调优实战 1. 引言&#xff1a;当AI开始设计AI 在图像分类任务中&#xff0c;我们常常陷入这样的困境&#xff1a;面对海量的网络结构选择和超参数组合&#xff0c;即使是有经…...