思想
用f[i][j][maxv][k]表示到达(i,j)获取的最大价值为maxv,取了k件宝贝的方案数实现记忆化搜索。注意,为了进入循环,我们需要在起始阶段赋值maxv=-1,搜索的时候把maxv+1。
代码
import java.io.*;
import java.util.Arrays;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static long[][][][] f = new long[55][55][15][15]; //f[i][j][maxv][k]表示到达(i,j)获取的最大价值为maxv,取了k件宝贝的方案数
static int n, m, k, mod = (int)1e9+7;
static int[][] g = new int[55][55];
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static long dfs(int x, int y, int maxv, int num){
if(f[x][y][maxv+1][num]!=-1) return f[x][y][maxv+1][num]; //记忆化,这里+1是因为我们是从-1开始搜索的,为了进入有效位置需要+1
//结束条件
if(x==n && y==m){
//终点的宝贝取不取的两种完成情况
if((maxv <g[x][y] && num==k-1) || (num==k)) return 1;
return 0;
}
if(x<1 || x>n || y<1 || y>m) return 0; //走出地图的情况
if(num>k) return 0; //宝贝取太多的情况
long res = 0;
//不取宝贝
res += dfs(x+1, y, maxv, num);
res += dfs(x, y+1, maxv, num);
//取宝贝的情况
if(g[x][y]>maxv){
res += dfs(x+1, y, g[x][y], num+1);
res += dfs(x, y+1, g[x][y], num+1);
}
return f[x][y][maxv+1][num]=res%mod;
}
public static void main(String[] args)throws IOException{
n = nextInt(); m = nextInt(); k = nextInt();
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++)
g[i][j] = nextInt();
}
//对f[][][][]初始化
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
for(int v=0; v<=14; v++){
Arrays.fill(f[i][j][v], -1);
}
}
}
out.println(dfs(1, 1, -1, 0));
out.flush();
out.close();
}
}