number-of-islandsV2.dart (1974B)
1 //This solution to the problem is not 2 //strictly better than the other merely it uses 3 //BFS instead of DFS to search the islands. 4 5 class Solution { 6 int numIslands(List < List < String >> grid) { 7 Set < String > travelled = {}; 8 int count = 0; 9 for (int i = 0; i < grid.length; ++i) { 10 for (int x = 0; x < grid[i].length; ++x) { 11 if (grid[i][x] == "0") { 12 continue; 13 } 14 if (travelled.contains(i.toString() + " " + x.toString())) { 15 continue; 16 } 17 traverse_island(grid, [i, x], travelled); 18 count += 1; 19 } 20 } 21 return count; 22 } 23 24 void traverse_island(List < List < String >> grid, List < int > position, Set < String > travelled) { 25 List < List < int >> queue = []; 26 queue.add(position); 27 while (queue.length > 0) { 28 int init_length = queue.length; 29 for (int i = 0; i < init_length; ++i) { 30 if (grid[queue[i][0]][queue[i][1]] == "0") { 31 continue; 32 } 33 String current_str = queue[i][0].toString() + " " + queue[i][1].toString(); 34 if (travelled.contains(current_str)) { 35 continue; 36 } 37 travelled.add(current_str); 38 if (queue[i][0] > 0) { 39 queue.add([queue[i][0] - 1, queue[i][1]]); 40 } 41 if (queue[i][1] > 0) { 42 queue.add([queue[i][0], queue[i][1] - 1]); 43 } 44 if (queue[i][0] < grid.length - 1) { 45 queue.add([queue[i][0] + 1, queue[i][1]]); 46 } 47 if (queue[i][1] < grid[queue[i][0]].length - 1) { 48 queue.add([queue[i][0], queue[i][1] + 1]); 49 } 50 51 } 52 queue = queue.sublist(init_length); 53 } 54 } 55 }