java代码之回溯法

解题思路:

每次行动判断下一步，

1、如果在边上，那么只有一个方向能走，所怀有最大gold大于当前物品，就只有一条路走，就是不拿，向唯一方向行动
2、跟1，不过最大gold小于当前，两条路，拿还是不拿
3、如果不在边上，两个方向，判断gold，如果大于，两条路，都是不拿走

4、跟3，不过最大gold小于当前，两个方向两种拿法，共四条路。

使用回溯，

终止条件，在右下角的时候判断

只跑出了示例，提交没跑出来，超时了。。。。。。。。

注意事项:

参考代码:

    static int s = 0;
    static int mod = 1000000007;
    static int n;
    static int m;
    static int k;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        //数组，坐标（用于检查是否是最后一点），最大值（用于判断行动），
        huisu(arr,0,0,0,0);
        System.out.println(s);
    }

    private static void huisu(int[][] arr, int i, int j, int g, int c) {
        //减枝，当所有物品大于k了，你肯定完成不了任务，因为你没有丢弃选项。
        if (c>k){
            return;
        }
        //终止条件
        if (i==n-1&&j==m-1){
            if (c==k){
                s++;
                s=s%mod;
                return;
            }else if (c==k-1&&g<arr[i][j]){
                s++;
                s=s%mod;
                return;
            }
            return;
        }
        //在边上
        if (i==n-1&&j<m-1){
            if (g>=arr[i][j]){
                huisu(arr,i,j+1,g,c);
                return;
            }
            huisu(arr,i,j+1,g,c);
            huisu(arr,i,j+1,arr[i][j],c+1);
            return;
        }
        //在边上
        if (j==m-1&&i<n-1){
            if (g>=arr[i][j]){
                huisu(arr,i+1,j,g,c);
                return;
            }
            huisu(arr,i+1,j,g,c);
            huisu(arr,i+1,j,arr[i][j],c+1);
            return;
        }
        
        //不在边上
        if (g>=arr[i][j]){
            huisu(arr,i,j+1,g,c);
            huisu(arr,i+1,j,g,c);
            return;
        }
        huisu(arr,i,j+1,g,c);
        huisu(arr,i,j+1,arr[i][j],c+1);
        huisu(arr,i+1,j,g,c);
        huisu(arr,i+1,j,arr[i][j],c+1);
        return;
    }