题目

类型：回溯

image.png

解题思路

枚举每个黄金点作为起点，然后使用 DFS 回溯搜索以该点作为起点所能得到的最大收益。

代码

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