leetcode

commit 3101b91b8641c8aecc523f056f81558831e62ee9
parent 45d87e4a57660548f207dbe2bb55e84b7515a5ca
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Fri, 19 May 2023 06:24:32 -0500

Completed number of islands problem using BFS instead of DFS

Diffstat:
A
number-of-islands/number-of-islandsV2.dart
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 55 insertions(+), 0 deletions(-)
diff --git a/number-of-islands/number-of-islandsV2.dart b/number-of-islands/number-of-islandsV2.dart
@@ -0,0 +1,55 @@
+//This solution to the problem is not
+//strictly better than the other merely it uses
+//BFS instead of DFS to search the islands.
+
+class Solution {
+    int numIslands(List < List < String >> grid) {
+        Set < String > travelled = {};
+        int count = 0;
+        for (int i = 0; i < grid.length; ++i) {
+            for (int x = 0; x < grid[i].length; ++x) {
+                if (grid[i][x] == "0") {
+                    continue;
+                }
+                if (travelled.contains(i.toString() + " " + x.toString())) {
+                    continue;
+                }
+                traverse_island(grid, [i, x], travelled);
+                count += 1;
+            }
+        }
+        return count;
+    }
+
+    void traverse_island(List < List < String >> grid, List < int > position, Set < String > travelled) {
+        List < List < int >> queue = [];
+        queue.add(position);
+        while (queue.length > 0) {
+            int init_length = queue.length;
+            for (int i = 0; i < init_length; ++i) {
+                if (grid[queue[i][0]][queue[i][1]] == "0") {
+                    continue;
+                }
+                String current_str = queue[i][0].toString() + " " + queue[i][1].toString();
+                if (travelled.contains(current_str)) {
+                    continue;
+                }
+                travelled.add(current_str);
+                if (queue[i][0] > 0) {
+                    queue.add([queue[i][0] - 1, queue[i][1]]);
+                }
+                if (queue[i][1] > 0) {
+                    queue.add([queue[i][0], queue[i][1] - 1]);
+                }
+                if (queue[i][0] < grid.length - 1) {
+                    queue.add([queue[i][0] + 1, queue[i][1]]);
+                }
+                if (queue[i][1] < grid[queue[i][0]].length - 1) {
+                    queue.add([queue[i][0], queue[i][1] + 1]);
+                }
+
+            }
+            queue = queue.sublist(init_length);
+        }
+    }
+}