题目

分析

这道题目和一般的回溯有些不同：
1.可以从任意一个地方出发，终止条件为四周没有可继续前进的路线（没有金矿或到达边界）。
2.我们并不需要记录每次前进的路径。只需要得到最大的金矿获得量。

所以首先是终止条件：

//如果所处在没有金矿的位置
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0)
 {
            return 0;
 }

其次如果是已经访问过的金矿，我们会将此地的值设置成0，然后在撤销的时候，恢复值，这里就是所谓的回溯了。

int value = grid[x][y];
grid[x][y] = 0;
//...前进到其他地方
grid[x][y] = value;

对于最大值：

public int select(int x, int y, int[][] grid) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
            return 0;
        }
        int res = 0;
        for (int[] dir : direct) {
            int value = grid[x][y];
            grid[x][y] = 0;
            res = Math.max(res, value + select(x + dir[0], y + dir[1], grid));
            grid[x][y] = value;
        }
        return res;
    }

整个select函数的作用，就是得到以x，y为起点，不断向四周寻找，直到到达为0 的地方，能得到的最大值。

完整代码：

public int getMaximumGold(int[][] grid) {
        if (grid.length == 0) return 0;
        if (grid[0].length == 0) return 0;
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0)
	            //试试所有起点，得到最大值
                    ans = Math.max(ans, select(i, j, grid));
            }
        }
        return ans;
    }
    //四个方向
    int[][] direct = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int select(int x, int y, int[][] grid) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
            return 0;
        }
        int res = 0;
        for (int[] dir : direct) {
            int value = grid[x][y];
            grid[x][y] = 0;
            res = Math.max(res, value + select(x + dir[0], y + dir[1], grid));
            grid[x][y] = value;
        }
        return res;
    }

虽然可能会出现select函数的参数完全相同的情况，但他们的结果肯定是不同的。这与动态规划的重叠子问题不同，因为每次的grid是不一样的。