你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

    为了使收益最大化，矿工需要按以下规则来开采黄金：

    每当矿工进入一个单元，就会收集该单元格中的所有黄金。
    矿工每次可以从当前位置向上下左右四个方向走。
    每个单元格只能被开采（进入）一次。
    不得开采（进入）黄金数目为 0 的单元格。
    矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

    示例 1：

    输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
    输出：24
    解释：
    [[0,6,0],
    [5,8,7],
    [0,9,0]]
    一种收集最多黄金的路线是：9 -> 8 -> 7。
    示例 2：

    输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
    输出：28
    解释：
    [[1,0,7],
    [2,0,6],
    [3,4,5],
    [0,3,0],
    [9,0,20]]
    一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

    提示：

    1 <= grid.length, grid[i].length <= 15
    0 <= grid[i][j] <= 100
    最多 25 个单元格中有黄金。

    1. class Solution {
    2.     boolean[][] st;
    3.     int n,m;
    4.     int[] dx = new int[]{-1,0,1,0}, dy = new int[]{0,1,0,-1};
    5.     public int getMaximumGold(int[][] grid) {
    6.         n = grid.length; m = grid[0].length;
    7.         st = new boolean[n][m];
    8.         int res = 0;
    9.         for (int i = 0; i < n; ++i) 
    10.             for (int j = 0; j < m; ++j) {
    11.                 if (grid[i][j] != 0) {
    12.                     st[i][j] = true;
    13.                     res = Math.max(res,dfs(i,j,grid));
    14.                     st[i][j] = false;
    15.                 }
    16.             }
    17.         return res;
    18.     }
    19.     public int dfs(int x, int y, int[][] grid) {
    20.         int res = 0;
    21.         for (int i = 0; i < 4; ++i) {
    22.             int a = x + dx[i], b = y + dy[i];
    23.             if (a < 0 || a >= n || b < 0 || b >= m) continue;
    24.             if (st[a][b]) continue;
    25.             if (grid[a][b] == 0) continue;
    26.             st[a][b] = true;
    27.             res = Math.max(res,dfs(a,b,grid));
    28.             st[a][b] = false;
    29.         }
    30.         return grid[x][y] + res;
    31.     }
    32. }