leetcode

commit c359b7671e6f7fec0fa1fbcc6ea495a7703d8005
parent 338d20982bed3cb50e2c3c1452b0107f4910c101
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 14 May 2023 13:35:30 -0500

Completed path with maximum gold using recursion

Diffstat:
A
path-with-maximum-gold/path-with-maximum-gold.dart
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 51 insertions(+), 0 deletions(-)
diff --git a/path-with-maximum-gold/path-with-maximum-gold.dart b/path-with-maximum-gold/path-with-maximum-gold.dart
@@ -0,0 +1,51 @@
+//This solution uses recursion to traverse through a matrix where each tile has gold and the 
+//player can only move one tile at a time. You need to return the highest amount of gold that can be 
+//collected without ever stepping on a spot that has 0 gold.
+//The time complexity of this code is O(4^n) where n is the number of values in the matrix.
+//Time: 1510ms Beats: 100%
+//Memory: 181.6MB Beats: 100%
+class Solution {
+  int getMaximumGold(List<List<int>> grid) {
+      int max = 0;
+      for(int i = 0 ; i < grid.length ; ++i){
+          for(int x = 0 ; x < grid[i].length ; ++x){
+              int current = getMax(grid, [i,x]);
+              if(current > max){
+                  max = current;
+              }
+          }
+      }
+      return max;
+  }
+
+  int getMax(List<List<int>> grid, List<int> current_pos){
+      if(current_pos[0] >= grid.length || current_pos[0] < 0){
+          return 0;
+      }
+      if(current_pos[1] >= grid[0].length || current_pos[1] < 0){
+          return 0;
+      }
+      if(grid[current_pos[0]][current_pos[1]] == 0){
+          return 0;
+      }
+      int current_val = grid[current_pos[0]][current_pos[1]];
+      List<List<int>> new_grid = [];
+      for(int i = 0 ; i < grid.length ; ++i){
+          new_grid.add(List.from(grid[i]));
+      }
+      new_grid[current_pos[0]][current_pos[1]] = 0;
+      int left = getMax(new_grid, [current_pos[0] -1 , current_pos[1]]);
+      int right = getMax(new_grid, [current_pos[0] +1, current_pos[1]]);
+      int up = getMax(new_grid, [current_pos[0] , current_pos[1] + 1]);
+      int down = getMax(new_grid, [current_pos[0] , current_pos[1] - 1]);
+      List<int> ls1 = [left,right,up,down];
+      int max = 0;
+      for(int i = 0 ; i < ls1.length ; ++i){
+          if(ls1[i] > max){
+              max = ls1[i];
+          }
+      }
+      return current_val + max;
+      
+  }
+}