leetcode

0 class Solution {

1 int n, m;

2 bool valid(const int x, const int y) { return x >= 0 && x < n && y >= 0 && y < m; }

3

4 int dfs(vector<vector<int>> &grid, const int x, const int y) {

5 static const int dir[] = {1, 0, -1, 0, 1};

6 int res = 0;

7

8 grid[x][y] = -grid[x][y];

9 for (int k = 0; k < 4; k++) {

10 const int i = x + dir[k + 1];

11 const int j = y + dir[k];

12 if (!valid(i, j) || grid[i][j] <= 0) continue;

13 res = max(res, dfs(grid, i, j));

14 }

15 grid[x][y] = -grid[x][y];

16 return grid[x][y] + res;

17 }

18

19 public:

20 int getMaximumGold(vector<vector<int>> &grid) {

21 n = grid.size(), m = grid[0].size();

22 int res = 0;

23 for (int i = 0; i < n; i++) {

24 for (int j = 0; j < m; j++)

25 res = max(res, dfs(grid, i, j));

26 }

27 return res;

28 }

29 };