注意:下面有两种代码,第二种是大部分人可以想到的,但是会超时,第一种就是记忆化搜索,
放两种代码的目的就是说明普通DFS和记忆化+DFS差的不多,便于大家参考学习。
参考代码:
#include<bits/stdc++.h> using namespace std; typedef long long LL; int n,m,k; int a[51][51]; LL jy[51][51][13][13]; //记忆化搜索 每个下标的含义与dfs函数一样 LL dfs(int x,int y,int num,int max){ //不等于-1就说明判断过这种情况,可以直接返回存过的值 if(jy[x][y][num][max+1]!=-1) return jy[x][y][num][max+1]; int lmax=a[x][y]; LL sum=0; if(x>n || y>m || num>k) return 0; if(x==n && y==m && (k==num || (num==k-1 && lmax>max))) return 1; if(lmax>max){ //拿宝物 sum+=dfs(x+1,y,num+1,lmax); sum+=dfs(x,y+1,num+1,lmax); } //不拿宝物 sum+=dfs(x+1,y,num,max); sum+=dfs(x,y+1,num,max); jy[x][y][num][max+1]=sum; //将这种情况存下来,加1是因为初始是-1,会越界,所以默认所有情况都加1 return sum%1000000007; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(jy,-1,sizeof(jy)); cin >> n >> m >> k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; cout << dfs(1,1,0,-1); return 0; } /* int a[51][51]; LL sum=0; int n,m,num; void DFS(int x,int y,int k,int max){ int lmax=a[x][y]; if(x==n && y==m && (k==num || (k==num-1 && lmax>max))){ sum++; sum=sum%1000000007; return; } if(x>n || y>m || k>num) return; if(lmax>max){ //拿宝物 DFS(x+1,y,k+1,lmax); DFS(x,y+1,k+1,lmax); } //不拿宝物 DFS(x+1,y,k,max); DFS(x,y+1,k,max); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> num; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; DFS(1,1,0,-1); cout << sum; return 0; } */
0.0分
1 人评分
C语言训练-角谷猜想 (C语言代码)浏览:1759 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:633 |
求组合数 (C语言代码)浏览:1195 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1437 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:877 |
字符逆序 (C语言代码)浏览:498 |
整数平均值 (C语言代码)浏览:843 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:981 |
排序算法(选择,插入,冒泡)浏览:874 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:590 |