leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

shortest-pathV2.dart (1970B)

      1 //This solution to the problem of moving from top left
      2 //to bottom right in the min number of moves uses BFS and
      3 //memoization which makes it quite a bit faster than DFS in this
      4 //context. It is still not great however because Dart does not have
      5 //a built in queue for leetcode so I had to make do with linear time queue 
      6 //removals for each iteration.
      7 
      8 //Time: 668ms Beats: 100%
      9 //Memory: 176MB Beats: 100%
     10 
     11 class Solution {
     12   int shortestPathBinaryMatrix(List<List<int>> grid) {
     13       Set<String> visited = {};
     14       List<List<int>> queue = [];
     15       queue.add([0,0]);
     16       int depth = 0;
     17       bool done = false;
     18       while(queue.length != 0 && done == false){
     19           int init_length = queue.length;
     20           for(int i = 0 ; i < init_length ; ++i){
     21               int curry = queue[i][1];
     22               int currx = queue[i][0];
     23               String current_str = curry.toString() + ' ' + currx.toString();
     24               if(visited.contains(current_str)){
     25                   continue;
     26               }
     27               visited.add(current_str);
     28               if(grid[currx][curry] == 1){
     29                   continue;
     30               }
     31               if(currx == grid.length - 1 && curry == grid[0].length - 1){
     32                   done = true;
     33                   break;
     34               }
     35               for(int x = -1 ; x <= 1 ; ++x){
     36                   for(int z = -1 ; z <= 1 ; ++z){
     37                       if(x == 0 && z == 0){
     38                           continue;
     39                       }
     40                       int new_x = currx + x;
     41                       int new_y = curry + z;
     42                       if(new_x < 0 || new_y < 0 || new_x >= grid.length || new_y >= grid[0].length){
     43                           continue;
     44                       }
     45                       queue.add([new_x, new_y]);
     46                   }
     47               }
     48           }
     49         queue = queue.sublist(init_length);
     50         depth += 1;
     51       }
     52       if(done){
     53         return depth;
     54       }
     55       return -1;
     56   }
     57 }