蓝桥杯2014年第五届真题-地宫取宝 （C++代码）

解题思路:

        搜索 + DP。

参考代码:

#include<bits/stdc++>h>
using namespace std;

const int MOD = 1000000007;
int Map[52][52];
int status[52][52][14][14];
int Maph, Mapw, quan;

int DFS(int posx, int posy, int total, int Maxvalue) {
	if (status[posx][posy][total][Maxvalue] != -1)
		return status[posx][posy][total][Maxvalue];
		
	if (posx == Maph && posy == Mapw) {
		if ((total == quan) || (total == quan - 1 && Map[Maph][Mapw] > Maxvalue))
			return status[posx][posy][total][Maxvalue] = 1;
		return status[posx][posy][total][Maxvalue] = 0;
	}

	int cnt = 0;
	if (posx < Maph) {
		if (Map[posx][posy] > Maxvalue)
			cnt = (cnt + DFS(posx + 1, posy, total + 1, Map[posx][posy])) % MOD;
		cnt = (cnt + DFS(posx + 1, posy, total, Maxvalue)) % MOD;
	}
	if (posy < Mapw) {
		if (Map[posx][posy] > Maxvalue)
			cnt = (cnt + DFS(posx, posy + 1, total + 1, Map[posx][posy])) % MOD;
		cnt = (cnt + DFS(posx, posy + 1, total, Maxvalue)) % MOD;
	}
	
	return status[posx][posy][total][Maxvalue] = cnt % MOD;
}

int main() {
	scanf("%d%d%d", &Maph, &Mapw, &quan);
	memset(status, -1, sizeof(status));
	for (int i1 = 1; i1 <= Maph; i1++)
		for (int i2 = 1; i2 <= Mapw; i2++) {
			scanf("%d", &Map[i1][i2]);
			Map[i1][i2]++;
		}
	printf("%d\n", DFS(1, 1, 0, 0));
}