本文共 3430 字，大约阅读时间需要 11 分钟。
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
思路1：DFS（1）
到达点已经判断完毕的类型，这种默认第一个点判断完毕，事实上我们第一个点不一定就是k个宝物之一 所以要两此dfs分别考虑要第一个点与不要第一个点的情况 #include #include #include #include #include const int INF = 0x3f3f3f3f;using namespace std;int n,m,k;int dir[2][2] = { {1,0},{0,1}};int map[51][51];long long ans;void dfs(int x,int y,int t,int mval) { if(t > k) return; if(x == n && y == m){ if(t == k) ++ans; return ; }// if(x+1 <= n){//// if(map[x][y] > m){// dfs(x+1,y,t+1,map[x][y]);// }// dfs(x+1,y,t,m);// }// if(y+1<= m){// if(map[x][y] > m){// dfs(x,y+1,t+1,map[x][y]);// }// dfs(x,y+1,t,m);// } for(int i = 0; i < 2; ++i){ //不同的下一步走法 int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(nx>=1 && nx<=n && ny>=1 && ny<=m){ if(map[nx][ny] > mval){ dfs(nx,ny,t+1,map[nx][ny]); dfs(nx,ny,t,mval); } else{ dfs(nx,ny,t,mval); } } } }int main() { scanf("%d%d%d",&n,&m,&k); ans = 0; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ scanf("%d",&map[i][j]); } } dfs(1,1,0,-INF);//这里是关键 dfs(1,1,1,map[1][1]); printf("%d\n",ans%1000000007); return 0; }
教训：开始把最大值变量名也记录为m，找了半天没找出错误，真是欲哭无泪啊 呜呜呜~ DFS（2）到达下一点判断前一点类型 ，这种类型不需要写两个dfs 因为到下一步才判断起点是否计算在内，这种需要注意的是当最后到达终点时候，终点的这个宝物并未判断是否也计算上，需要多加个判断条件 t == k-1&&max < a[x][y]
#include long long ans;int n,m,k;int a[55][55];const int INF=0x3f3f3f3f;void dfs(int x,int y,int pre,int max){ if(pre>k) return ; if(x==n-1&&y==m-1) { if(pre==k||(pre==k-1&&max max) dfs(x+1,y,pre+1,a[x][y]); dfs(x+1,y,pre,max); } if(y max) dfs(x,y+1,pre+1,a[x][y]); dfs(x,y+1,pre,max); }}int main(){ while(~scanf("%d%d%d",&n,&m,&k)) { for(int i=0; i
加1是因为题目可能有的宝物价值就是0，但是我们默认初始化地图的值为0，也就是如果不加1，当我们遇见宝物价值为0 的就会产生错误，但是题目意思是可以价值为0的宝物的。错误原因在于我们搜索的时候默认价值初始价值为0（价值为0的宝物默认被我们抛弃了~~~）
#include #include #define M 1000000007using namespace std; typedef long long ll;ll dp[52][52][15][15];ll map[52][52];int n,m,k;int dfs(int x,int y,int num,ll max_val) { if(dp[x][y][num][max_val] != -1) return dp[x][y][num][max_val]; int res = 0; if(x == n-1 && y == m-1){ if(num == k || (num == k-1) && map[x][y] > max_val){ ++res; } return dp[x][y][num][max_val] = res; } if(x+1 < n){ if(map[x][y] > max_val){ res += dfs(x+1,y,num+1,map[x][y]); res %= M; } res += dfs(x+1,y,num,max_val); res %= M; } if(y+1 < m){ if(map[x][y] > max_val){ res += dfs(x,y+1,num+1,map[x][y]); res %= M; } res += dfs(x,y+1,num,max_val); res %= M; } return dp[x][y][num][max_val] = res;//记录当前 x,y,num,max_val下的结果 } int main() { cin >> n >> m >> k; for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ cin >> map[i][j]; ++map[i][j]; } } memset(dp,-1,sizeof(dp)); ll ans = dfs(0,0,0,0); cout << ans%M; return 0; }
转载地址：http://lqimi.baihongyu.com/