leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1219.cpp (894B)

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 };