fork download
copy 
  1.         #include <iostream>
  2.         #include <vector>
  3.         #include <algorithm>
  4.         using namespace std;
  5.  
  6.         int findMaxBeauty(vector<vector<int>>& grid, int x, int y, int n, 
  7.                           vector<vector<bool>>& visited) {
  8.             // Base cases
  9.             if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y]) 
  10.                 return -1e9;
  11.  
  12.             if (x == n-1 && y == n-1) 
  13.                 return grid[x][y];
  14.  
  15.             // Mark current cell as visited
  16.             visited[x][y] = true;
  17.  
  18.             // Try all possible moves: right, down, up
  19.             int maxPath = -1e9;
  20.             maxPath = max(maxPath, findMaxBeauty(grid, x, y+1, n, visited));  // right
  21.             maxPath = max(maxPath, findMaxBeauty(grid, x+1, y, n, visited));  // down
  22.             maxPath = max(maxPath, findMaxBeauty(grid, x-1, y, n, visited));  // up
  23.  
  24.             // Unmark the cell (backtrack)
  25.             visited[x][y] = false;
  26.  
  27.             // Return result
  28.             return grid[x][y] + maxPath;
  29.         }
  30.  
  31.         int getMaximumBeauty(int n, vector<vector<int>>& grid) {
  32.             vector<vector<bool>> visited(n, vector<bool>(n, false));
  33.             return findMaxBeauty(grid, 0, 0, n, visited);
  34.         }
  35.  
  36.         int main() {
  37.             int n = 3;
  38. 		    vector<vector<int>> grid = {
  39. 		        {1, 18, -10},
  40. 		        {-1, -18, -18},
  41. 		        {5, 2, 2}
  42. 		    };
  43.  
  44.             cout << getMaximumBeauty(n, grid) << endl;
  45.             return 0;
  46.         }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
https://ideone.com/nBfYEK
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!