注意:下面有两种代码,第二种是大部分人可以想到的,但是会超时,第一种就是记忆化搜索,
放两种代码的目的就是说明普通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语言代码)浏览:599 |
printf基础练习2 (C语言代码)浏览:599 |
C语言训练-角谷猜想 (C语言代码)浏览:1717 |
多输入输出练习1 (C语言代码)浏览:1190 |
ASCII帮了大忙浏览:749 |
C语言训练-大、小写问题 (C语言代码)浏览:615 |
简单的for循环浏览:1421 |
C语言训练-亲密数 (C语言代码)浏览:682 |
母牛的故事 (C语言代码)浏览:551 |
出圈】指针malloc版浏览:355 |