49 lines
1.2 KiB
C++
49 lines
1.2 KiB
C++
// lanqiao 216 地宫寻宝
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
const ll p = 1e9 + 7;
|
|
const int N = 55;
|
|
int n, m, k, c[N][N];
|
|
int dx[] = {0, 1};
|
|
int dy[] = {1, 0};
|
|
int dp[N][N][15][15];
|
|
|
|
bool inmp(int x, int y){
|
|
return x >= 1 && x <= n && y >= 1 && y <= m;
|
|
}
|
|
|
|
// 表示从(1,1)到(x, y), 总共有cnt件宝贝, 且最大值为max的方案数
|
|
ll dfs(int x, int y, int mx, int cnt){
|
|
if(x == n && y == m) return (ll)(cnt == k);
|
|
if(dp[x][y][mx][cnt] != -1) return dp[x][y][mx][cnt];
|
|
|
|
ll res = 0;
|
|
for(int i = 0; i < 2; i++){
|
|
int nx = x + dx[i], ny = y + dy[i];
|
|
if(!inmp(nx, ny)) continue;
|
|
// 拿宝贝
|
|
if(c[nx][ny] > mx && cnt < k) res = (res + dfs(nx, ny, c[nx][ny], cnt + 1)) % p;
|
|
//不拿宝贝
|
|
res = (res + dfs(nx, ny, mx, cnt)) % p;
|
|
}
|
|
return dp[x][y][mx][cnt] = res;
|
|
}
|
|
|
|
int main(){
|
|
memset(dp, -1, sizeof dp);
|
|
cin >> n >> m >> k;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= m; j++){
|
|
cin >> c[i][j];
|
|
c[i][j]++;
|
|
}
|
|
}
|
|
cout << (dfs(1,1,0,0) + dfs(1,1,c[1][1],1)) % p << '\n';
|
|
return 0;
|
|
}
|
|
/* test samples 1 -> 2
|
|
2 2 2
|
|
1 2
|
|
2 1
|
|
*/ |