1212. 地宫取宝

标签：1212 map val int dfs step 地宫 include 取宝

https://www.acwing.com/problem/content/description/1214/

先说暴搜做法
结果:会超时..能过三个点,但是是一种思路

#include<algorithm>
#include<iostream>
#include<iostream>
#include<cstring>
using namespace std;
const int N =105;
int map[N][N],f[N][N];
int n,m,k;
int ans;
void dfs(int i,int j,int step,int v)
{
	if(i>n || j >m || step > k )return;
	if(i==n && j==m)
		if(step == k || (step+1==k && map[i][j]>v ))
	    {
            ans++;
            return;
	    }
	if(map[i][j] > v)
	{
		dfs(i+1,j,step,v);
		dfs(i,j+1,step,v);
		dfs(i+1,j,step+1,map[i][j]);
		dfs(i,j+1,step+1,map[i][j]);
	}
	else
	{
		dfs(i+1,j,step,v);
		dfs(i,j+1,step,v);
	}
}

int main()
{
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin >> map[i][j];
	dfs(1,1,0,-1);
	cout << ans%1000000007 << endl;
	return 0;
}

DP做法

#include<algorithm>
#include<iostream>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 55;
const int MOD = 1e9 + 7;
int map[N][N], f[N][N][15][15];
int n, m, k;
int ans;
int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
		    cin >> map[i][j];
		    map[i][j]++;
		}
	f[1][1][1][map[1][1]] = 1;
	f[1][1][0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (i == 1 && j == 1)continue;
			for (int u = 0; u <= k; u++)
				for (int v = 0; v <= 13; v++)
				{
					int &val = f[i][j][u][v];
					val = (val + f[i - 1][j][u][v]) % MOD;
					val = (val + f[i][j - 1][u][v]) % MOD;
					if (u > 0 && v == map[i][j])
					{
						for (int c = 0; c < v; c++)
						{
							val = (val + f[i - 1][j][u - 1][c]) % MOD;
							val = (val + f[i][j - 1][u - 1][c]) % MOD;
						}
					}
				}
		}
	for(int i=0;i<=13;i++)ans=(ans+f[n][m][k][i])%MOD;
	cout << ans << endl;
	return 0;
}

标签：1212,map,val,int,dfs,step,地宫,include,取宝
From： https://www.cnblogs.com/lxl-233/p/16739172.html