深度优先搜索 洛谷P1123取数游戏 解题思路
2022/1/2 23:10:48
本文主要是介绍深度优先搜索 洛谷P1123取数游戏 解题思路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 题目
- 题解
- AC代码
- 改进
- 改进代码
- 经验总结
本人萌新一枚,如果有地方错误的话还请各位看官在评论区留言指正。
(。・∀・)ノ゙
题目
一个N ×M的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
输入格式
第1行有一个正整数TT,表示了有TT组数据。
对于每一组数据,第一行有两个正整数NN和MM,表示了数字矩阵为NN行MM列。
接下来NN行,每行MM个非负整数,描述了这个数字矩阵。
输出格式
TT行,每行一个非负整数,输出所求得的答案。
样例
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
题解
DFS
每一个dfs()选取一个数,到无可选的数时,比较当前当前结果pMax和最终结果Max,更新Max
一些问题:
1.先选0号位再选3号位,和先选3号位再选0号位实际上是一样的效果,如何避免不必要的计算?
先选低号位,再选高号位,也可以看作是一个剪枝。
实现:父节点选择一个数后,把该数后面一个位置i传给子节点参数,子节点从i开始选择,不可向前选择
2.父节点如何把信息(哪些位置不可选)传递给子结点?
引入全局数组pos[]记录各个位置是否可选,为1表示可选,为0表示不可选。
父函数选择一个数后对pos[]进行更改,再调用子函数,需要注意的是,由于我采用的是全局变量(pos),从子函数返回后要对父函数本次对pos的操作进行回退,采用全局变量的好处是递归时减少传参耗费的时间。
AC代码
#include <iostream> #include <string.h> #include <algorithm> #include <vector> using namespace std; int T; int N, M; int D[6+1][6+1];//用于存储每一组数据 int Max, pMax;//Max是当前这组的结果,pMax保存当前这一组DFS中每一条路径的中间结果 int pos[6*6+5];//用于记录位置信息,pos[i] = 1表示从二维数组D开始位置编号,第i号(从0开始编号)当前是否可被选择 void dfs(int k){ if(k >= N*M){ Max = max(Max, pMax); return; } int flag = 0; for(int i=k; i<N*M; i++){ if(pos[i]){ //选择第i个位置 flag = 1; int row, cow; row = i/M; cow = i-M*row; pMax += D[row][cow]; //下面置i的右方,左下方,下方,右下方为0 int mem[4] = {0}; int old[4] = {0}; if(i+1<N*M && (i+1)/M == row){ //右方 old[0] = pos[i+1]; pos[i+1] = 0; mem[0] = 1; } if(i+M-1<N*M && (i+M-1)/M == row+1){ //左下方 old[1] = pos[i+M-1]; pos[i+M-1] = 0; mem[1] = 1; } if(i+M < N*M){ //下方 old[2] = pos[i+M]; pos[i+M] = 0; mem[2] = 1; } if(i+M+1<N*M && (i+M+1)/M == row+1){ //右下方 old[3] = pos[i+M+1]; pos[i+M+1] = 0; mem[3] = 1; } dfs(i+1); //下面对pMax和pos进行回退 pMax -= D[row][cow]; if(mem[0]){ pos[i+1] = old[0]; } if(mem[1]){ pos[i+M-1] = old[1]; } if(mem[2]){ pos[i+M] = old[2]; } if(mem[3]){ pos[i+M+1] = old[3]; } } } if(!flag){ //没有可选择的数了,直接比较结果 Max = max(Max, pMax); } } void init(){ //初始化一些信息 Max = pMax = 0; for(int i=0; i<N*M; i++){ pos[i] = 1; } } void gmn(){ init(); dfs(0); } int main(int argc, char *argv[]) { cin>>T; for(int i=0; i<T; i++){ cin>>N>>M; for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ cin>>D[i][j]; } } gmn(); cout<<Max<<endl; } return 0; }
改进
本题由于数据范围比较小,对递归次数的要求并不是很高,实际上还可以进行剪枝,比如在选择几个数据之后,可能会在这几个数之间留下空隙,例如:
数据:
23 21 34 87 22
24 34 33 98 35
33 88 98 78 67
32 78 19 23 76
假如依次选择23、22、33、98、76,这样的话,第一行第三列的34就是可选但没有选的数,由于本题求的是最大的总和,那么该方法求的结果必然不是最大的。
我改进的想法:定期对是否存在空隙进行检查,如果存在则直接剪枝,由于每一行至多影响到上一行,也就是说每一行至多填满上一行的空隙,无法填满之前的,所以可以在每一次调用dfs(i)时,都对i所在行的上一行的上一行进行检测,若找到空隙则进行剪枝。
由于我之前取数只是对该数后面的位置进行pos=0的操作,所以采用该方法时,要对该数所在的九宫格的所有数的位置都进行pos=0.
改进代码
#include <iostream> #include <string.h> #include <algorithm> #include <vector> using namespace std; int T; int N, M; int D[6+1][6+1];//用于存储每一组数据 int Max, pMax;//Max是当前这组的结果,pMax保存当前这一组DFS中每一条路径的中间结果 int pos[6*6+5];//用于记录位置信息,pos[i] = 1表示从二维数组D开始位置编号,第i号(从0开始编号)当前是否可被选择 //int Counts; void dfs(int k){ //Counts++; if(k >= N*M){ Max = max(Max, pMax); return; } int r = k/M; if(r-2>=0){ r -= 2; for(int i=0; i<M; i++){ if(pos[r*M+i]){ return; } } } int flag = 0; for(int i=k; i<N*M; i++){ if(pos[i]){ //选择第i个位置 flag = 1; int row, cow; row = i/M; cow = i-M*row; pMax += D[row][cow]; int mem[8] = {0}; int old[8] = {0}; if(i+1<N*M && (i+1)/M == row){ //右方 old[0] = pos[i+1]; pos[i+1] = 0; mem[0] = 1; } if(i+M-1<N*M && (i+M-1)/M == row+1){ //左下方 old[1] = pos[i+M-1]; pos[i+M-1] = 0; mem[1] = 1; } if(i+M < N*M){ //下方 old[2] = pos[i+M]; pos[i+M] = 0; mem[2] = 1; } if(i+M+1<N*M && (i+M+1)/M == row+1){ //右下方 old[3] = pos[i+M+1]; pos[i+M+1] = 0; mem[3] = 1; } pos[i] = 0;//本身 if(i-1 >= 0 && (i-1)/M == row){ //左侧 old[4] = pos[i-1]; pos[i-1] = 0; mem[4] = 1; } if(i-M-1 >= 0 && (i-M-1)/M == row-1){ //左上方 old[5] = pos[i-M-1]; pos[i-M-1] = 0; mem[5] = 1; } if(i-M >= 0){ //上方 old[6] = pos[i-M]; pos[i-M] = 0; mem[6] = 1; } if(i-M+1 >= 0 && (i-M+1)/M == row-1){ //右上方 old[7] = pos[i-M+1]; pos[i-M+1] = 0; mem[7] = 1; } dfs(i+1); //下面对pMax和pos进行回退 pMax -= D[row][cow]; if(mem[0]){ pos[i+1] = old[0]; } if(mem[1]){ pos[i+M-1] = old[1]; } if(mem[2]){ pos[i+M] = old[2]; } if(mem[3]){ pos[i+M+1] = old[3]; } pos[i] = 1; if(mem[4]){ pos[i-1] = old[4]; } if(mem[5]){ pos[i-M-1] = old[5]; } if(mem[6]){ pos[i-M] = old[6]; } if(mem[7]){ pos[i-M+1] = old[7]; } } } if(!flag){ //没有可选择的数了,直接比较结果 Max = max(Max, pMax); } } void init(){ //初始化一些信息 Max = pMax = 0; for(int i=0; i<N*M; i++){ pos[i] = 1; } } void gmn(){ init(); dfs(0); } int main(int argc, char *argv[]) { cin>>T; for(int i=0; i<T; i++){ cin>>N>>M; for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ cin>>D[i][j]; } } gmn(); cout<<Max<<endl; } //cout<<Counts<<endl; return 0; }
改进前测试用例需要调用dfs()360次,改进后只用了276次,其实改进的并不多(lll¬ω¬),大家有什么更好的方法可以在评论区一起交流一下,本萌新很乐意回复哦(๑•̀ㅂ•́)و✧
经验总结
做题的时候回退那个地方一开始有错,卡了半天,被这个全局变量的方法坑到了,进行回退的时候,如果当前函数置pos[i]=0,我就回退为pos[i] = 1,实际上pos[i]可能一开始为0,置pos[i]=0后又回退为1就发生了错误,应该是回退为0.
这也给我留了个教训o(╥﹏╥)o:回退时如果是A=B的形式一定要慎重考虑,A之前是否为B
这篇关于深度优先搜索 洛谷P1123取数游戏 解题思路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南