弗莱

#include<stdio.h>
    #include<string.h>
    int a[55][55]={0};//数据矩阵 
    int b[55][55]={0};//标记矩阵，0表示可以走，此题需要回溯 
    int index=0;//方案数类型
    int n,m,k;
    int c[2]={1,0},d[2]={0,1}; //偏移矩阵 
    void dfs(int x,int y,int max,int flog)
    {
    	if(flog==k&&x==n&&y==m)
    	{
    		index++;
    		index%=1000000007;
    		return;
    	}
    	b[x][y]=1;
    	for(int i=0;i<2;i++)
    	{
    		int p=x+c[i];
    		int q=y+d[i];
    		if(p>0&&q>0&&p<=n&&q<=m&&b[p][q]==0&&flog<=k)//剪枝 
    		{
    			if(a[p][q]<=max)//不能拿 
    			{
    				dfs(p,q,max,flog);//直接走 
    			}
    			else
    			{
    				dfs(p,q,max,flog);//选择不拿，走 
    				dfs(p,q,a[p][q],flog+1);//选择拿 
    			}
    		}
    	}
    	b[x][y]=0; 
    }
    
    int main()
    {
    	scanf("%d%d%d",&n,&m,&k);
    	for(int i=1;i<=n;i++)//录入 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	dfs(1,1,0,0);//起点、手中最大价值物品、当前的件数 (开始不拿)
    	dfs(1,1,a[1][1],1);//开始拿 
    	printf("%d\n",index%1000000007);
    }

###### ##### 不出意料，在37的时候时间超限

# 2：dp
###### 没太大头绪，参考了好多大佬的代码写的

#include<stdio.h>
    #define mod 1000000007
    int Max=13;
    int N,M,K;
    int a[55][55]={0};//价值矩阵
    int index[55][55][13][13]={0}; 
    
    void dp()
    {
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=M;j++)
    		{
    			for(int k=0;k<=K;k++)
    			{
    				for(int c=0;c<Max;c++)
    				{
    					if(i==1&&j==1)
    					{
    						if(k==0||(k==1&&c>a[i][j]))
    						{
    							index[i][j][k][c]=1;
    						}
    						continue;
    					}
    					int temp0=0,temp1=0;
    					if(k>0&&c>a[i][j])
    					{
    						temp0=(index[i-1][j][k-1][a[i][j]]+index[i][j-1][k-1][a[i][j]])%mod;//拿 
    					}
    					temp1= (index[i-1][j][k][c]+index[i][j-1][k][c])%mod;
    					index[i][j][k][c]=(temp1+temp0)%mod;
    				}
    			}
    		}
    	}
    }
    
    int main()
    {
    	scanf("%d%d%d",&N,&M,&K);
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=M;j++)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	dp();
    	printf("%d\n",index[N][M][K][12]);
    	
    }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

弗莱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言考试练习题_保留字母（C语言代码）

A+B for Input-Output Practice (V) （C++代码）

编写题解 1436: 蓝桥杯2014年第五届真题-地宫取宝 dfs vs dp

评论区

精彩推荐

十->二进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

弗莱

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言考试练习题_保留字母 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

编写题解 1436: 蓝桥杯2014年第五届真题-地宫取宝 dfs vs dp

评论区

精彩推荐

十->二进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

十->二进制转换（C语言代码）

求圆的面积（C语言代码）

C二级辅导-分段函数（C语言代码）