nikunjsoni

1219

Jul 13th, 2021
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int dfs(vector<vector<int>>& g, int i, int j) {
  4.       if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] <= 0)  return 0;
  5.       g[i][j] = -g[i][j];
  6.       auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
  7.       g[i][j] = -g[i][j];
  8.       return g[i][j] + res;
  9.     }
  10.     int getMaximumGold(vector<vector<int>>& grid, int res = 0) {
  11.       for (auto i = 0; i < grid.size(); ++i)
  12.         for (auto j = 0; j < grid[i].size(); ++j)
  13.           res = max(res, dfs(grid, i, j));
  14.       return res;
  15.     }
  16. };
RAW Paste Data