shortest-path.dart (1637B)
1 //Given a matrix of 1's and 0's return 2 //the shortest path from 0,0 to the bottom right 3 //of the grid. To do this I used DFS and recursion with 4 //memoization. This is too slow however because the correct 5 //way to do these types of searches is with queues either 6 //BFS or djikstra with a priority queue (heap) 7 //Time: TLE 8 //Memory: TLE 9 class Solution { 10 int shortestPathBinaryMatrix(List<List<int>> grid) { 11 return traverse(grid, [0,0], 1, {}); 12 } 13 int traverse(List<List<int>> grid, List<int> position, int depth, Map<String,int> memo){ 14 int posx = position[0]; 15 int posy = position[1]; 16 if(grid[posx][posy] == 1){ 17 return -1; 18 } 19 if(posx == grid.length - 1 && posy == grid[0].length - 1){ 20 return depth; 21 } 22 String current_str = posx.toString() + ' ' + posy.toString(); 23 if(memo.containsKey(current_str)){ 24 if((memo[current_str] ?? 0) <= depth){ 25 return -1; 26 } 27 } 28 memo[current_str] = depth; 29 int return_int = -1; 30 for(int i = -1 ; i <= 1 ; ++i){ 31 for(int x = -1 ; x <= 1 ; ++x){ 32 int newx = posx + i; 33 int newy = posy + x; 34 if(newx < 0 || newy < 0 || newx >= grid.length || newy >= grid[0].length || (x == 0 && i == 0)){ 35 continue; 36 } 37 int current = traverse(grid, [newx, newy] , depth + 1, memo); 38 if(current != -1){ 39 if(current < return_int || return_int == -1){ 40 return_int = current; 41 } 42 } 43 } 44 } 45 return return_int; 46 } 47 }