#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int maxn = 100; const long long INF = 1000000007; //用来取余 int maze[maxn][maxn]; int d[52][52][14][14]; //行,列,k个数,value int n, m, k; //[n,m], k件宝贝 long long ans; //方案数 int dfs(int r, int c, int sum, int Max); //当前位置 void input(); void solve(); void input() { memset(d, -1, sizeof(d)); scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &maze[i][j]); } } } int dfs(int r, int c, int sum, int Max) { if (d[r][c][sum][Max + 1] != -1) { //已经遍历完, 并设置了结果 return d[r][c][sum][Max + 1]; //返回结果 } int t = 0; if (r == n - 1 && c == m - 1) { //到达入口 if (maze[r][c] > Max) { //可以再拿一个宝物 if (sum == k || sum == k - 1) //如果已经到了 k 或是 k-1，方案++ t++; } else if (sum == k) { //不能拿时候,则此时就需要为k, 方案++ t++; } return d[r][c][sum][Max + 1] = t; //更新方案数 } if (r + 1 < n) { if (maze[r][c] > Max) { //可以拿 t += dfs(r + 1, c, sum + 1, maze[r][c]); //选择拿 t %= INF; t += dfs(r + 1, c, sum, Max); //选择不拿 t %= INF; } else { t += dfs(r + 1, c, sum, Max); //不可以拿 t %= INF; } } if (c + 1 < m) { if (maze[r][c] > Max) { t += dfs(r, c + 1, sum + 1, maze[r][c]); t %= INF; t += dfs(r, c + 1, sum, Max); t %= INF; } else { t += dfs(r, c + 1, sum, Max); t %= INF; } } d[r][c][sum][Max + 1] = t; //将方案数 保存在Max + 1 处 return d[r][c][sum][Max + 1]; //返回方案数 } void solve() { input(); ans = dfs(0, 0, 0, -1); cout << ans << endl; } int main() { solve(); return 0; }