path-with-maximum-gold.dart (1763B)
1 //This solution uses recursion to traverse through a matrix where each tile has gold and the 2 //player can only move one tile at a time. You need to return the highest amount of gold that can be 3 //collected without ever stepping on a spot that has 0 gold. 4 //Time: 1510ms Beats: 100% 5 //Memory: 181.6MB Beats: 100% 6 class Solution { 7 int getMaximumGold(List<List<int>> grid) { 8 int max = 0; 9 for(int i = 0 ; i < grid.length ; ++i){ 10 for(int x = 0 ; x < grid[i].length ; ++x){ 11 int current = getMax(grid, [i,x]); 12 if(current > max){ 13 max = current; 14 } 15 } 16 } 17 return max; 18 } 19 20 int getMax(List<List<int>> grid, List<int> current_pos){ 21 if(current_pos[0] >= grid.length || current_pos[0] < 0){ 22 return 0; 23 } 24 if(current_pos[1] >= grid[0].length || current_pos[1] < 0){ 25 return 0; 26 } 27 if(grid[current_pos[0]][current_pos[1]] == 0){ 28 return 0; 29 } 30 int current_val = grid[current_pos[0]][current_pos[1]]; 31 List<List<int>> new_grid = []; 32 for(int i = 0 ; i < grid.length ; ++i){ 33 new_grid.add(List.from(grid[i])); 34 } 35 new_grid[current_pos[0]][current_pos[1]] = 0; 36 int left = getMax(new_grid, [current_pos[0] -1 , current_pos[1]]); 37 int right = getMax(new_grid, [current_pos[0] +1, current_pos[1]]); 38 int up = getMax(new_grid, [current_pos[0] , current_pos[1] + 1]); 39 int down = getMax(new_grid, [current_pos[0] , current_pos[1] - 1]); 40 List<int> ls1 = [left,right,up,down]; 41 int max = 0; 42 for(int i = 0 ; i < ls1.length ; ++i){ 43 if(ls1[i] > max){ 44 max = ls1[i]; 45 } 46 } 47 return current_val + max; 48 49 } 50 }