蓝桥杯2014省赛《地宫寻宝》100%数据全过代码

ゝ一世哀愁。 2022-04-23 14:42 125阅读 0赞

备赛重要, 先放代码, 题解有时间再写.

#include<stdio.h>
    #include<string.h> 
    #define MOD 1000000007
    int N = 0;
    int M = 0;
    int K = 0;
    // 存放输入地图 
    int num[51][51] = { 0}; 
    
    // 存放路径结果 
    unsigned long long count_array[51][51] = { 0}; 
    
    // 开一个bool 4维数组
    // 前两维表示x, y
    // 后面一个表示k值, 用来减少搜索, 
    // 如果k已经存在 那么不用继续搜索了, 直接+1种情况, 
    // 如果不存在就记录, 并且继续搜索 
    // 最后面一个是当前k值下拿到的最大宝物数 
    int cache[51][51][13][13] = { 0};
    
    
    unsigned long long count = 0;
    // 直接搜索 
    void dfs_1(int n, int x, int y, int max){ 
    	if(x >= M || y >= N) return;
    	
    	if(num[y][x] > max && n < K){ // 可以拿就拿 
    		// 剪枝 
    		if(n + 1 == K){ 	// 如果拿起后就够了 直接加上次数 防止不必要的搜索了 
    			count += count_array[y][x];
    			count %= MOD;
    		}else{ 
    			int temp = max;
    			max = num[y][x];
    			dfs_1(n + 1, x + 1, y, max);
    			dfs_1(n + 1, x, y + 1, max);
    			max = temp;
    		}
    	}
    	// 不可以拿, 或者可以拿却不拿 
    	dfs_1(n, x + 1, y, max);
    	dfs_1(n, x, y + 1, max);	
    	
    }
    // 记忆式搜索 
    long long dfs_4(int n, int x, int y, int max){ 
    	// 限定边界 
    	if(x >= M || y >= N) return 0;
    	
    	// 查看表， 如果表已经有数据， 表示正在遍历一个重复的节点， 直接返回结果 
    	if(cache[y][x][n][max] != 0){ 
    		return cache[y][x][n][max];
    	} 
    	// 注: 为当前节点所有子节点结果之和
    	// 取到和 之后，然后存放进表， 如果以后表里面有数据， 那么就可以直接使用 
    	long long sum = 0; 
    	if(num[y][x] > max && n < K){ // 可以拿就拿 
    		if(n + 1 == K){ 	// 如果拿起后就够了 直接加上次数 防止不必要的搜索了 
    			// 这里是唯一的出口 
    			sum += count_array[y][x];
    		}else{ 
    			int temp = max;
    			max = num[y][x];
    			
    			sum += dfs_4(n + 1, x + 1, y, max);
    			sum %= MOD;
    			sum += dfs_4(n + 1, x, y + 1, max);
    			sum %= MOD;
    			
    			max = temp;
    		}
    	}
    	// 不可以拿, 或者可以拿却不拿 
    	sum += dfs_4(n, x + 1, y, max);
    	sum %= MOD;
    	sum += dfs_4(n, x, y + 1, max);	
    	
    	cache[y][x][n][max] = sum % MOD;
    	return sum % MOD;
    }
    
    
    int main(){ 
    	
    	scanf("%d %d %d", &N, &M, &K);
    	for(int i= 0; i < N; i++){ 
    		for(int j = 0; j < M; j++){ 
    			scanf("%d", &num[i][j]);
    		}
    	}// 输入结束 
    	
    	// 计算次数矩阵 
    	// 用来剪掉 已经找到k件宝物的结果， 使其不再继续搜索， 直接得出答案 
    	count_array[N - 1][M] = 1;
    	for(int i = N - 1; i >= 0; --i){ 
    		for(int j = M - 1; j >= 0; --j){ 
    			count_array[i][j]  = count_array[i + 1][j] + count_array[i][j + 1];
    			count_array[i][j] %= MOD;
    		}
    	}
    	
    	dfs_1(0, 0, 0, 0);
    	printf("直接搜索结果: %lld\n", count); 
    	// 计算答案 
    	long long ans = dfs_4(0, 0, 0, 0);
     
    	printf("记忆搜索结果: %lld\n", ans);
    	
    	return 0;
    }