minimum-time-to-visit.dart (1941B)
1 //Find the minimum time required to make it from the top 2 //left to the bottom right of a matrix assuming you can 3 //only move to a space if the current step number is greater than 4 //or equal to the value in the tile. 5 //The problem with this solution is with big numbers this 6 //recursive solution has to recurse very far. As such this gives a stack 7 //overflow error. 8 //Time: N/A 9 //Memory: N/A 10 class Solution { 11 int minimumTime(List<List<int>> grid) { 12 return recurse(grid, [0,0] , 0); 13 } 14 15 int recurse(List<List<int>> grid, List<int> current_position, int step){ 16 int currentx = current_position[0]; 17 int currenty = current_position[1]; 18 int current_val = grid[currentx][currenty]; 19 if(current_val > step){ 20 return -1; 21 } 22 23 if(currentx == grid.length - 1 && currenty == grid[currentx].length - 1){ 24 return 0; 25 } 26 int shortest_path = -1; 27 if(currentx != grid.length - 1){ 28 shortest_path = recurse(grid , [currentx + 1, currenty], step + 1); 29 } 30 if(currenty != grid[currentx].length - 1){ 31 int current = recurse(grid , [currentx, currenty + 1], step + 1); 32 if(shortest_path == -1 || current < shortest_path && current != -1){ 33 shortest_path = current; 34 } 35 } 36 if(shortest_path != -1){ 37 return shortest_path + 1; 38 } 39 if(currenty != 0){ 40 int current = recurse(grid , [currentx, currenty - 1], step + 1); 41 if(shortest_path == -1 || current < shortest_path && current != -1){ 42 shortest_path = current; 43 } 44 } 45 if(currentx != 0){ 46 int current = recurse(grid , [currentx - 1, currenty], step + 1); 47 if(shortest_path == -1 || current < shortest_path && current != -1){ 48 shortest_path = current; 49 } 50 } 51 if(shortest_path == -1){ 52 return -1; 53 } 54 return shortest_path + 1; 55 } 56 }