AcWing 1212. 地宫取宝
原题链接
中等
作者:
海里长蘑菇
,
2024-04-08 13:54:42
,
所有人可见
,
阅读 1
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
int n,m,k;
int v[N][N];
int f[N][N][13][14];
int mod = 1000000007;
int main()
{
cin>>n>>m>>k;
for(int i = 1 ; i <=n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cin>>v[i][j];
v[i][j]++;
}
}
f[1][1][1][v[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; // if( i == i && j == 1) continue;
for(int a = 0 ; a <= k; a++) // for(int a = 0 ; a <= k a++)
{
for(int b = 0 ; b <= 13 ;b++) // 害我找的好久,多一点就算不出来叼你老母 for(int b = 0 ; b <= 14 ;b++)
{
int &ww = f[i][j][a][b]; // int ww = &f[i][j][a][b];
ww = (ww + f[i-1][j][a][b])%mod;
ww = (ww +f[i][j-1][a][b])%mod;
if(a>0&&b == v[i][j])
{
for(int c = 0 ; c < b ; c++ ) //for(int c = 1 ; c <= b ; c++ )
{ //数据保证合法,但是实际情况上,会有b = 0 的情况发生
ww = (ww + f[i-1][j][a-1][c])%mod; //解决问题要从实际上出发,满足实际才是对的
ww = (ww + f[i][j-1][a-1][c])%mod;
}
}
}
}
}
}
int ans = 0 ;
for(int i = 0 ;i <= 13;i++)
ans = (ans +f[n][m][k][i])%mod;
cout<<ans<<endl;
return 0 ;
}