X The king has an underground treasure house , yes n×m A lattice matrix , Put one baby in each grid , Every baby has a value tag .

The entrance to the underground palace is in the upper left corner , The exit is in the lower right corner .

Xiao Ming is taken to the entrance of the underground palace , The king asked him to walk only to the right or down .

When walking through a grid , If the value of the treasure in that grid is greater than any treasure in Xiaoming's hand , Xiao Ming can pick it up （ of course , You can also not take it ）.

When Xiao Ming came to the exit , If the baby in his hand happens to be k piece , Then these babies can be given to Xiao Ming .

Please help Xiao Ming calculate , In a given situation , How many different courses of action can he get this k Piece baby .

Input format
first line 3 Integer ,n,m,k, See the title description for the meaning .

next n that 's ok , Each line has m Integer Ci Used to describe the treasure value of each grid of the treasure matrix .

Output format
Output an integer , Indicates that it is exactly taken k Number of baby action plans .

The figure may be large , Output it to 1000000007 Results of mold taking .

Data range
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
sample input 1：
2 2 2
1 2
2 1
sample output 1：
2
sample input 2：
2 3 2
1 2 3
2 1 5
sample output 2：
14

Problem solving ideas ：

First we define dp[i][j][cnt][k] Xiao Ming walks from the upper left corner to (i,j) Take it cnt Items with a maximum value of k How to walk , The range of values in this problem is (0,12), It means that items at all points of the map may have value 0, So when we read in the data , Put every data +1, So the scope of value becomes (1,13), It is convenient for us to consider the initialization problem , Then we think about relational expressions , You can take or not take at this point , If you don't take it , The code is as follows ：
dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD; dp[i][j][
cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;
Write it separately here , And the results have to be %MOD, Otherwise, the data will explode , Then every time Xiao Ming takes something bigger than the one in front of him , then , If the items at this point can be taken , Must match ：

The value of this item is equal to us dp[i][j][cnt][k] Medium k value , And if you take things , that cnt Must be greater than 0, Then we have to consider how to initialize , At the starting point , Xiao Ming may take this item , It's also possible not to take this item , So just don't take it dp
= 1, Take this item dp[w]

The code is as follows ：
#include <iostream> using namespace std; const int N = 55; const int MOD =
1000000007; int dp[N][N]; int w[N][N]; int n, m, k; int main() { cin >>
n>> m >> k; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> w
[i][j]; w[i][j]++; } dp = 1; dp[w] = 1; for (int i =
1; i <= n; i++) for (int j = 1; j <= m; j++) for (int cnt = 0; cnt <= k; cnt++)
for (int v = 0; v <= 13; v++) { dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1]
[j][cnt][v]) % MOD; dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v])
% MOD; if (cnt > 0 && w[i][j] == v) { for (int s = 0; s < v; s++) { dp[i][j][cnt
][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt - 1][s]) % MOD; dp[i][j][cnt][v] = (
dp[i][j][cnt][v] + dp[i][j - 1][cnt - 1][s]) % MOD; } } } int res = 0; for (int
i= 0; i <= 13; i++) { res = (res + dp[n][m][k][i]) % MOD; } cout << res << endl;
return 0; }

Technology
Daily Recommendation
views 2