leetcode

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

01-matrixV2.dart (2615B)

      1 //Memoized version using bfs searching from each 0. This again
      2 //does not work because there are some lists with lots of 0's in them.
      3 //Time: TLE
      4 //Memory: TLE
      5 class Solution {
      6   List<List<int>> updateMatrix(List<List<int>> mat) {
      7       List<List<int>> answers = [];
      8       for(int i = 0 ; i < mat.length ; ++i){
      9           answers.add([]);
     10           for(int x = 0 ; x < mat[i].length ; ++x){
     11               answers[i].add(-1);
     12           }
     13       }
     14 
     15       for(int i = 0 ; i < answers.length ; ++i){
     16           for(int x = 0 ; x < answers[0].length ; ++x){
     17               if(mat[i][x] == 0){
     18                 set_distances([i,x], mat, answers);
     19               }
     20           }
     21       }
     22       return answers;
     23   }
     24 
     25   void set_distances(List<int> find, List<List<int>> matrix, List<List<int>> distances){
     26       List<List<int>> search_vals = [];
     27       Set<String> visited = {};
     28       distances[find[0]][find[1]] = 0;
     29       if(find [0] > 0){
     30           search_vals.add([find[0] - 1, find[1]]);
     31       }
     32       if(find[1] > 0){
     33           search_vals.add([find[0], find[1] - 1]);
     34       }
     35       if(find[0] < matrix.length - 1){
     36           search_vals.add([find[0] + 1, find[1]]);
     37       }
     38       if(find[1] < matrix[0].length - 1){
     39           search_vals.add([find[0], find[1] + 1]);
     40       }
     41       int dist = 1;
     42 
     43       while(search_vals.length > 0){
     44           int init_len = search_vals.length;
     45           for(int i = 0 ; i < init_len ; ++i){
     46             List<int> current = search_vals[i];
     47             int currentx = current[0];
     48             int currenty = current[1];
     49 
     50             if(visited.contains(currentx.toString() + " " + currenty.toString())){
     51                 continue;
     52             }
     53             visited.add(currentx.toString() + " " + currenty.toString());
     54 
     55 
     56             if(matrix[currentx][currenty] == 0){
     57                 distances[currentx][currenty] = 0;
     58                 continue;
     59             }
     60             if(dist < distances[currentx][currenty] || distances[currentx][currenty] == -1){
     61                 distances[currentx][currenty] = dist;
     62             }
     63             
     64             if(currentx > 0){
     65                 search_vals.add([currentx - 1, currenty]);
     66             }
     67             if(currenty > 0){
     68                 search_vals.add([currentx, currenty - 1]);
     69             }
     70             if(currentx < matrix.length - 1){
     71                 search_vals.add([currentx + 1, currenty]);
     72             }
     73             if(currenty < matrix[0].length - 1){
     74                 search_vals.add([currentx, currenty + 1]);
     75             }
     76 
     77           }
     78           dist += 1;
     79           search_vals = search_vals.sublist(init_len);
     80       }
     81 
     82 
     83 
     84   }
     85 
     86 
     87      
     88 }