1219 黄金矿工

public class one_two_one_nine_黄金矿工 {

    @Test
    public void test(){
        int[][] grid = {{0,6,0},
                        {5,8,7},
                        {0,9,0}};
        int result = getMaximumGold(grid);
        System.out.println(result);
    }

    private int res = 0;

    public int getMaximumGold(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                backtrace(grid, i, j, 0);
            }
        }
        return res;
    }

    public void backtrace(int[][] grid, int x, int y, int money){
        if (!check(grid, x, y)) return ;
        if (grid[x][y] == 0){   //结束条件：四面为0，实际上是踏过去之后所在地为0
            res = Math.max(res, money);
            return ;
        }
        //做选择
        int stored = grid[x][y];
        money += stored;
        grid[x][y] = 0; //不走回头路
        //for循环有限，枚举代替递归
        backtrace(grid, x - 1, y, money);
        backtrace(grid, x, y - 1, money);
        backtrace(grid, x + 1, y, money);
        backtrace(grid, x, y + 1, money);
        //撤销
        money -= stored;
        grid[x][y] = stored;
    }

    public boolean check(int[][] grid, int x, int y){
        return (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length );
    }
}

public class duxiaoman_002_坚强的小昆虫 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int group = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < group; i++) {   //每一组
            flag = false;
            res = Integer.MAX_VALUE;
            String[] temp = sc.nextLine().split(" ");
            int n = Integer.parseInt(temp[0]);
            int m = Integer.parseInt(temp[1]);
            int x = 0, y = 0;   //初始位置
            char[][] matrix = new char[n][m];
            for (int j = 0; j < n; j++) {
                matrix[j] = sc.nextLine().toCharArray();
                for (int k = 0; k < matrix[j].length; k++) {
                    if (matrix[j][k] == '@'){
                        x = j;
                        y = k;
                    }
                }
            }
            //处理完输入，进入正式逻辑
            backtrace(matrix, x, y, 0);
            if (!flag) res = -1;
            System.out.println(res);
        }
    }

    private static int res = Integer.MAX_VALUE;
    private static boolean flag = false;

    /**
     * 回溯
     * @param matrix
     */
    public static void backtrace(char[][] matrix, int x, int y, int num){
        if (matrix[x][y] == '#') return ;
        if (matrix[x][y] == '*') num++;
        //结束条件
        if (x == 0 || y == 0 || x == matrix.length - 1 || y == matrix[0].length - 1){
            res = Math.min(res, num);
            flag = true;
            return ;
        }
        //四次枚举代替for循环
        char stored = matrix[x][y] == '@' ? '.' : matrix[x][y];
        matrix[x][y] = '#'; //不走回头路！
        backtrace(matrix, x - 1, y, num);   //上
        backtrace(matrix, x, y - 1, num);   //左
        backtrace(matrix, x + 1, y, num);   //下
        backtrace(matrix, x, y + 1, num);   //右
        matrix[x][y] = stored;
    }
}