leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1219.cpp (894B)

      1 class Solution {
      2     int n, m;
      3     bool valid(const int x, const int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      4 
      5     int dfs(vector<vector<int>> &grid, const int x, const int y) {
      6         static const int dir[] = {1, 0, -1, 0, 1};
      7         int res = 0;
      8 
      9         grid[x][y] = -grid[x][y];
     10         for (int k = 0; k < 4; k++) {
     11             const int i = x + dir[k + 1];
     12             const int j = y + dir[k];
     13             if (!valid(i, j) || grid[i][j] <= 0) continue;
     14             res = max(res, dfs(grid, i, j));
     15         }
     16         grid[x][y] = -grid[x][y];
     17         return grid[x][y] + res;
     18     }
     19 
     20   public:
     21     int getMaximumGold(vector<vector<int>> &grid) {
     22         n = grid.size(), m = grid[0].size();
     23         int res = 0;
     24         for (int i = 0; i < n; i++) {
     25             for (int j = 0; j < m; j++)
     26                 res = max(res, dfs(grid, i, j));
     27         }
     28         return res;
     29     }
     30 };