1219. 黄金矿工

之前写过一个类似的，这种回溯的其实并不用对sum进行设置：

class Solution {

    int ml = 0;

    private void dfs(int[][] grid, int i, int j, boolean sign[][], int sum){

        ml = Math.max(ml, sum);

        // 如果出界
        if(i < 0 || j < 0 || i == grid.length || j == grid[0].length){
            return;
        }

        // 如果没有黄金
        if(grid[i][j] == 0){
            return;
        }

        // 如果遍历过
        if(sign[i][j]){
            return;
        }


        // 否则
        sign[i][j] = true;

        dfs(grid, i+1, j, sign, sum+grid[i][j]);
        dfs(grid, i, j+1, sign, sum+grid[i][j]);
        dfs(grid, i-1, j, sign, sum+grid[i][j]);
        dfs(grid, i, j-1, sign, sum+grid[i][j]);


        sign[i][j] = false;

    }


    public int getMaximumGold(int[][] grid) {

        int rows = grid.length;
        int columns = grid[0].length;

        boolean sign[][] = new boolean[grid.length][grid[0].length];

        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                if(grid[i][j] != 0){
                    dfs(grid, i, j, sign, 0);
                }
            }
        }

        return ml;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.getMaximumGold(new int[][]{
                {1,0,7},
                {2,0,6},
                {3,4,5},
                {0,3,0},
                {9,0,20}
        });
    }
}