01-matrix.dart (2572B)
1 //Find the distance to the nearest 0 for every cell 2 //and return back a matrix with those distances. 3 //This implementation is too slow because of the List.from(visited) 4 //which basically makes it so that certain tiles will be revisited. 5 //This is necessary however because I am using dfs so a tile may 6 //be visited but in a suboptimal way to arrive there. To fix this 7 //the best thing to do would be to use bfs instead of dfs. 8 //Time: TLE 9 //Memory :TLE 10 class Solution { 11 List<List<int>> mat = []; 12 List<List<int>> answers = []; 13 List<List<int>> updateMatrix(List<List<int>> matrix) { 14 mat = matrix; 15 for(int i = 0; i < mat.length ; ++i){ 16 answers.add(List.filled(mat[0].length , -1)); 17 } 18 for(int i = 0 ; i < answers.length ; ++i){ 19 for(int x = 0 ; x < answers[0].length ; ++x){ 20 answers[i][x] = recurse([i,x], []); 21 } 22 } 23 24 return answers; 25 } 26 27 int recurse(List<int> position, List<String> visited){ 28 if(answers[position[0]][position[1]] != -1){ 29 return answers[position[0]][position[1]]; 30 } 31 visited.add(position[0].toString() + " " + position[1].toString()); 32 if(mat[position[0]][position[1]] == 0){ 33 return 0; 34 } 35 int min_dist = -1; 36 bool left = visited.contains((position[0] - 1).toString() + " " + position[1].toString()); 37 bool right = visited.contains((position[0] + 1).toString() + " " + position[1].toString()); 38 bool up = visited.contains(position[0].toString() + " " + (position[1] - 1).toString()); 39 bool down = visited.contains(position[0].toString() + " " + (position[1] + 1).toString()); 40 //left,3, 41 if(position[0] > 0 && !left){ 42 int current = recurse([position[0] - 1, position[1]], List.from(visited)); 43 if(current < min_dist || min_dist == -1){ 44 min_dist = current; 45 } 46 } 47 //right 48 if(position[0] < mat.length - 1 && !right){ 49 int current = recurse([position[0] + 1, position[1]] , List.from(visited)); 50 if(current < min_dist || min_dist == -1){ 51 min_dist = current; 52 } 53 } 54 //up 55 if(position[1] > 0 && !up){ 56 int current = recurse([position[0], position[1] - 1] , List.from(visited)); 57 if(current < min_dist || min_dist == -1){ 58 min_dist = current; 59 } 60 } 61 //down 62 if(position[1] < mat[0].length - 1 && !down){ 63 int current = recurse([position[0], position[1] + 1] , List.from(visited)); 64 if(current < min_dist || min_dist == -1){ 65 min_dist = current; 66 } 67 } 68 if(min_dist == -1){ 69 return 1000000000; 70 } 71 return min_dist + 1; 72 } 73 }