P1123 取数游戏(dfs算法)

2024-04-07 23:52
文章标签 算法 游戏 dfs 取数 p1123

本文主要是介绍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算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/884019

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS?优势:应用场景:DFS配置步骤什么是DFS?DFS指的是分布式文件系统(Distr

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python开发围棋游戏的实例代码(实现全部功能)

《Python开发围棋游戏的实例代码(实现全部功能)》围棋是一种古老而复杂的策略棋类游戏,起源于中国,已有超过2500年的历史,本文介绍了如何用Python开发一个简单的围棋游戏,实例代码涵盖了游戏的... 目录1. 围棋游戏概述1.1 游戏规则1.2 游戏设计思路2. 环境准备3. 创建棋盘3.1 棋盘类

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第