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

P1123 取数游戏(dfs算法)

题目描述

一个 N×M 的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻 8个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。

输入格式

第一行有一个正整数 T,表示了有 T 组数据。

对于每一组数据,第一行有两个正整数 N 和 M,表示了数字矩阵为 N 行 M 列。

接下来 N 行,每行 M 个非负整数,描述了这个数字矩阵。

输出格式

共 T 行,每行一个非负整数,输出所求得的答案。

输入输出样例

输入 

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

输出 

271
172
99

数据范围及约定

  • 对于20%20%的数据,1≤N,M≤3;
  • 对于40%40%的数据,1≤N,M≤4;
  • 对于60%60%的数据,1≤N,M≤5;
  • 对于100%100%的数据,1≤N,M≤6,1≤T≤20。

思路 : 

此题为n皇后问题的简单版,算法为dfs,只要枚举每行每列元素就可,分两种情况,取这个元素和不能取这个元素,题目中所说的,相邻的八个格子元素不能取是这个意思如图

×的八个方向不能取。接下来我们看代码


AC代码: 

#include<iostream>
#include<cmath>
#include<cstring>using namespace std;int dx[8] = {-1,-1,-1,0,0,1,1,1},dy[8] = {-1,0,1,-1,1,-1,0,1};
const int N = 10;
int g[N][N];//数字数组 
int st[N][N];//标记数组 
int mx,ans,n,m;void dfs(int x,int y)
{//如果搜到该行的最后一列就换下一行第一列 if(y == m + 1){x++,y=1;}//所有行列搜完了 进行输出 if(x == n + 1){mx = max(ans,mx);return; }//不放 dfs(x,y+1);//放if(!st[x][y]){ans += g[x][y];for(int i=0;i<8;i++){st[x+dx[i]][y+dy[i]]++;}dfs(x,y+1);for(int i=0;i<8;i++){st[x+dx[i]][y+dy[i]]--;}ans -= g[x][y];} 
}int main()
{cin.tie(0)->ios::sync_with_stdio(false);//快读 int t;cin >> t;while(t --){//注意:每次使用完记得清0 memset(g,0,sizeof(g));memset(st,0,sizeof(st));cin >> n >> m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin >> g[i][j];}}mx = 0;//每次搜完需要变成0,方便下次使用不会错 dfs(1,1);//从第一个行第一列第一个元素开始搜索 cout << mx << endl;}return 0;
}

注意:此题我们不能使用bool类型去进行标记,我们可以用一个int类型的变量来记录,当这个数被访问时,该变量自增,当回溯时,该变量自减==>所以当该变量为零时,该数未被访问。(至于这个我们可以手动模拟一下就能有结果)

相关文章:

P1123 取数游戏(dfs算法)

题目描述 一个 NM 的由非负整数构成的数字矩阵&#xff0c;你需要在其中取出若干个数字&#xff0c;使得取出的任意两个数字不相邻&#xff08;若一个数字在另外一个数字相邻 8个格子中的一个即认为这两个数字相邻&#xff09;&#xff0c;求取出数字和最大是多少。 输入格式 第…...

交叉验证(Cross-Validation)

交叉验证的基本概念 交叉验证通常用于评估机器学习模型在未知数据上的性能。它将数据集分成k个不同的子集&#xff0c;然后进行k次训练和验证。在每次迭代中&#xff0c;选择一个子集作为测试集&#xff0c;其余的子集作为训练集。这样&#xff0c;每个子集都用作过测试集&…...

【kears】(01)keras使用介绍

文章目录 一.特点二.keras如何支持TensorFlow、CNTK 和 Theano2.1 使用 TensorFlow 后端引擎训练和评估模型2.2 使用 TensorFlow 后端引擎训练和评估模型2.3 使用 Theano后端引擎训练和评估模型2.4 不同深度学习框架如何选择1.1 keras.datasets&#xff1a;包含多种常用数据集1…...

2. TypeScript 安装与环境配置指南

TypeScript 是 JavaScript 的一个超集&#xff0c;它为 JavaScript 增加了类型系统和对 ES6 的支持。TypeScript 不仅能够帮助开发者捕获代码中的错误&#xff0c;还能提供更好的编辑器支持&#xff0c;包括代码补全、接口提示等。本文将详细介绍如何在您的开发环境中安装和配置…...

python pygame库的略学

文章目录 概述1. pygame的初始化和退出2. 创建游戏窗口&#xff08;1&#xff09;set_mode()&#xff08;2&#xff09;set_capyion()&#xff08;3&#xff09;update() 3. 游戏循坏与游戏时钟4. 图形和文本绘制&#xff08;1&#xff09;图形绘制&#xff08;2&#xff09;文…...

大模型日报2024-04-09

大模型日报 2024-04-09 大模型资讯 苹果预告超越ChatGPT的新AI模型ReaLM 摘要: 苹果公司最新宣布&#xff0c;即将推出一款名为ReaLM的人工智能模型。这款AI技术在理解复杂屏幕用户指令方面表现出高超的能力&#xff0c;并能与用户进行自然流畅的对话。ReaLM的推出预示着苹果在…...

抖音视频如何下载保存(方法分享)

有时刷抖音视频&#xff0c;看的喜欢的视频想要下载到本地&#xff0c;但是有很多视频无法下载或者下载下来是有水印的&#xff0c;那怎么办呢?   抖音视频下载有两种情况&#xff1a; 一种是可以直接点击分享下载&#xff0c;然后可以直接点击保存到相册。 视频就自动下载…...

MySQL-用户与权限管理:用户管理、权限管理、角色管理

用户与权限管理 用户与权限管理1.用户管理1.1 登录MySQL服务器1.2 创建用户1.3 修改用户1.4 删除用户1.5 设置当前用户密码1.6 修改其它用户密码 2. 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 访问控制连接核实阶段请求核实阶段 3. 角色管理…...

Vue.js中如何使用Vue Router处理浏览器返回键的功能

在Vue.js中&#xff0c;Vue Router默认提供了处理浏览器返回键的功能。当用户点击浏览器的返回键时&#xff0c;Vue Router会自动导航到历史记录中的上一个路由。然而&#xff0c;如果你想自定义返回键的行为或者在特定的页面上进行特殊处理&#xff0c;你可以使用Vue Router的…...

QT drawPixmap和drawImage处理图片模糊问题

drawPixmap和drawImage显示图片时&#xff0c;如果图片存在缩放时&#xff0c;会出现模糊现象&#xff0c;例如将一个100x100 的图片显示到30x30的区域&#xff0c;这个时候就会出现模糊。如下&#xff1a; 实际图片&#xff1a; 这个问题就是大图显示成小图造成的像素失真。 当…...

YOLOv9改进策略 :小目标 | 新颖的多尺度前馈网络(MSFN) | 2024年4月最新成果

💡💡💡本文独家改进:多尺度前馈网络(MSFN),通过提取不同尺度的特征来增强特征提取能力,2024年最新的改进思路 💡💡💡创新点:多尺度前馈网络创新十足,抢先使用 💡💡💡如何跟YOLOv8结合:1)放在backbone后增强对全局和局部特征的提取能力;2)放在detect…...

从零开始:一步步学习爬虫技术的实用指南(一)

从零开始&#xff1a;一步步学习爬虫技术的实用指南&#xff08;一&#xff09; Urllib1.什么是互联网爬虫2.爬虫核心3.爬虫的用途4.爬虫的分类4.1 通用爬虫&#xff1a;4.1 聚焦爬虫&#xff1a; 5.反爬手段5.1 User‐Agent&#xff1a;5.2.代理IP5.3.验证码访问5.4.动态加载网…...

Python面向对象详解

文章目录 类和继承变量保护类装饰器 类和继承 Python虽然以函数式著称&#xff0c;但在Python中&#xff0c;万物皆对象&#xff0c;其对面向对象编程是有着非常不错的支持的。类是面向对象的核心数据类型&#xff0c;下面代码就创建了一个Person类。 class Person:count 0d…...

思维题锻炼-最小数字

思维题锻炼-最小数字 目录题目描述输入样例输出样例代码 目录 题目描述 给一串数字&#xff0c;求出最小的整数&#xff0c;不能是原数字串中的数字&#xff0c;也不能由数字串中的数字相加得到 输入样例 5 2 1输出样例 4代码 #include<bits/stdc.h> #include<s…...

ubuntu20.04 运行 lio-sam 流程记录

ubuntu20.04 运行 lio-sam 一、安装和编译1.1、安装 ROS11.2、安装 gtsam1.3、安装依赖1.4、下载源码1.5、修改文件1.6、编译和运行 二、官方数据集的运行2.1、casual_walk_2.bag2.2、outdoor.bag、west.bag2.3、park.bag 三、一些比较好的参考链接 记录流程&#xff0c;方便自…...

P5356 [Ynoi2017] 由乃打扑克

我手把手教她打扑克 qwq 综合分析一下2个操作&#xff0c;查找区间第k小的值&#xff0c;感觉可以用主席树&#xff0c;区间修改那没事了 考虑分块做法,块长B 分析第一个操作 只需要维护数列的单调性&#xff0c;然后二分答案上二分就ok了 分析第二个操作 维护一个加法懒…...

随机潮流应对不确定性?计及分布式发电的配电系统随机潮流计算程序代码!

前言 随着分布式电源在电力系统中所占比例的不断扩大,研究分布式发电对系统稳态运行的影响势在必行。带分布式发电的潮流计算常常用来评估其并网后对系统的影响&#xff0c;同时它也是分析分布式发电对电网稳定性的影响等其他理论研究工作的基础。然而&#xff0c;许多分布式发…...

Oracle表空间满清理方案汇总分享

目录 前言思考 一、第一种增加表空间的数据文件数量达到总容量的提升 二、第二种解决方案针对system和sysaux的操作 2.1SYSTEM表空间优化 2.2sysaux表空间回收 2.2.1针对sysaux的表空间爆满还有第二套方案维护 三、第三种解决方案使用alter tablespace resize更改表空间的…...

基于单片机数码管20V电压表仿真设计

**单片机设计介绍&#xff0c;基于单片机数码管20V电压表仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机数码管20V电压表仿真设计的主要目的是通过单片机和数码管显示电路实现一个能够测量0到20V直流电压的电…...

SCI一区 | Matlab实现NGO-TCN-BiGRU-Attention北方苍鹰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测

SCI一区 | Matlab实现NGO-TCN-BiGRU-Attention北方苍鹰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测 目录 SCI一区 | Matlab实现NGO-TCN-BiGRU-Attention北方苍鹰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测预测效果基本介绍模型…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...