洛谷 P1123 取数游戏(dfs)
2022/9/7 23:26:42
本文主要是介绍洛谷 P1123 取数游戏(dfs),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://www.luogu.com.cn/problem/P1123
题目大意:给定一个n*m的矩阵,问我们从里面怎样取能取到最大的总和? 条件是选了一个数,下次它的八个方向上的数字就不能选了
输入 #1复制 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 输出 #1复制 271 172 99
注意这是多组输入
dfs模板题
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=200200,M=2002; const int INF=0x3f3f3f3f; LL n,m; LL sum,maxn=0; LL a[M][M]; LL vis[M][M]; LL dx[]={-1,-1,-1,0,0,1,1,1},dy[]={1,0,-1,1,-1,1,0,-1}; void dfs(LL x,LL y) { if(y==m+1)//当需要换下一行的时候,直接跳到下一行 { dfs(x+1,1); return ; } if(x==n+1)//当都结束了的时候,直接对比一下最大值 { maxn=max(maxn,sum); return ; } dfs(x,y+1);//默认选不起这个所以我们不选这个 if(vis[x][y]==0)//瞥一眼发现可以选欸 { sum+=a[x][y];//选出来 for(LL i=0;i<8;i++)//标记一下四周已经不能再被选了 ++vis[x+dx[i]][y+dy[i]]; dfs(x,y+1);//接着往下寻找可选的地方 for(LL i=0;i<8;i++) --vis[x+dx[i]][y+dy[i]];//状态回溯,没准别的地方才是我们真正需要的,所以需要状态回溯 sum-=a[x][y];//总数相应减去 } } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); LL T=1; cin>>T; while(T--) { maxn=0,sum=0; memset(a,0,sizeof a); memset(vis,0,sizeof vis); cin>>n>>m; for(LL i=1;i<=n;i++) for(LL j=1;j<=m;j++) cin>>a[i][j]; dfs(1,1);//从第一行第一列开始从左往右,从上往下开始寻找 cout<<maxn<<endl; } return 0; }
这篇关于洛谷 P1123 取数游戏(dfs)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署