AcWing 1212. 地宫取宝
原题链接
中等
作者:
K_683
,
2024-04-08 19:46:40
,
所有人可见
,
阅读 1
import java.io.*;
public class Main {
public static void main(String[] args)throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
int n,m,k;
int MOD = 1000000007 ;
st.nextToken();
n = (int)st.nval;
st.nextToken();
m = (int)st.nval;
st.nextToken();
k = (int)st.nval;
int[][] arr = new int[n+10][m+10];
int[][][][] dp = new int[55][55][15][15];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
st.nextToken();
arr[i][j] = (int)st.nval;
arr[i][j]++;
}
}
dp[1][1][1][arr[1][1]] = 1;//初始化第一个数,拿的情况
dp[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 l = 0; l <= k; l++) {//拿取的物品数量
for (int o = 0; o <= 13; o++) {//不拿物品
dp[i][j][l][o] = ( dp[i][j][l][o] + dp[i-1][j][l][o] ) % MOD;//向下走
dp[i][j][l][o] = ( dp[i][j][l][o] + dp[i][j-1][l][o] ) % MOD;//向右走
if(l > 0 && o == arr[i][j]){// 背包还有剩余空间且当前物品可以拿
for (int p = 0; p < o; p++) {
dp[i][j][l][o] = (dp[i][j][l][o] + dp[i-1][j][l-1][p] ) % MOD;
dp[i][j][l][o] = (dp[i][j][l][o] + dp[i][j-1][l-1][p] ) % MOD;
}
}
}
}
}
}
int ans = 0;
for (int i = 1; i <= 13; i++) {
ans = (ans + dp[n][m][k][i] ) % MOD;
}
pw.println(ans);
pw.flush();
}
}