number-of-islands.dart (1763B)
1 //Find the number of islands contained in a matrix 2 //where the string "0" represents water and "1" represents 3 //land. To do this I used DFS to travel through each 4 //island that is found by iterating through the matrix and then 5 //placing the travelled 1's into a set for O(1) search. 6 //The time complexity of this is O(m*n) where m is the height 7 //and n is the width of the matrix. 8 //Time: 353ms Beats: 24% 9 //Memory: 180.4MB Beats: 8% 10 11 class Solution { 12 int numIslands(List<List<String>> grid) { 13 Set<String> travelled = {}; 14 int count = 0; 15 for(int i = 0 ; i < grid.length ; ++i){ 16 for(int x = 0 ; x < grid[i].length ; ++x){ 17 if(grid[i][x] == "0"){ 18 continue; 19 } 20 if(traverse_island(grid, [i,x], travelled)){ 21 count += 1; 22 } 23 } 24 } 25 return count; 26 } 27 28 bool traverse_island(List<List<String>> grid , List<int> position, Set<String> travelled){ 29 if(grid[position[0]][position[1]] == "0"){ 30 return false; 31 } 32 String current_str = position[0].toString() + " " + position[1].toString(); 33 if(travelled.contains(current_str)){ 34 return false; 35 } 36 travelled.add(current_str); 37 if(position[0] + 1 != grid.length){ 38 traverse_island(grid, [position[0] + 1, position[1]], travelled); 39 } 40 if(position[0] - 1 != -1){ 41 traverse_island(grid, [position[0] - 1, position[1]], travelled); 42 } 43 if(position[1] + 1 != grid[position[0]].length){ 44 traverse_island(grid, [position[0], position[1] + 1], travelled); 45 } 46 if(position[1] - 1 != -1){ 47 traverse_island(grid, [position[0], position[1] - 1], travelled); 48 } 49 return true; 50 } 51 52 }