This approach uses Depth-First Search (DFS) to explore the grid. We iterate over each cell in the grid, and every time we find an unvisited '1', it indicates the discovery of a new island. We then perform DFS from that cell to mark all the connected '1's as visited, effectively marking the entire island.
Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.
1#include <stdbool.h>
2
3void dfs(char** grid, int r, int c, int gridSize, int* gridColSize) {
4 if (r < 0 || c < 0 || r >= gridSize || c >= gridColSize[r] || grid[r][c] == '0') {
5 return;
6 }
7 grid[r][c] = '0';
8 dfs(grid, r-1, c, gridSize, gridColSize);
9 dfs(grid, r+1, c, gridSize, gridColSize);
10 dfs(grid, r, c-1, gridSize, gridColSize);
11 dfs(grid, r, c+1, gridSize, gridColSize);
12}
13
14int numIslands(char** grid, int gridSize, int* gridColSize) {
15 int numIslands = 0;
16 for (int i = 0; i < gridSize; i++) {
17 for (int j = 0; j < gridColSize[i]; j++) {
18 if (grid[i][j] == '1') {
19 numIslands++;
20 dfs(grid, i, j, gridSize, gridColSize);
21 }
22 }
23 }
24 return numIslands;
25}The function dfs is responsible for marking connected '1's as visited by changing them to '0'. The numIslands function traverses each cell in the grid, and upon finding a '1', it increments the count and triggers a DFS from that cell to mark the entire island.
This approach uses Breadth-First Search (BFS) to traverse the grid. Similar to DFS, we treat each '1' as a node in a graph. On encountering a '1', we initiate a BFS to explore all connected '1's (island nodes) by utilizing a queue for the frontier, marking them in-place as visited.
Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.
1using System.Collections.Generic;
2
3public class Solution {
4 private static readonly int[][] directions = new int[][] {
5 new int[] {-1, 0}, new int[] {1, 0},
6 new int[] {0, -1}, new int[] {0, 1},
7 };
8
9 public int NumIslands(char[][] grid) {
10 if (grid == null || grid.Length == 0) {
11 return 0;
12 }
13 int numIslands = 0;
14 for (int r = 0; r < grid.Length; r++) {
15 for (int c = 0; c < grid[0].Length; c++) {
16 if (grid[r][c] == '1') {
17 numIslands++;
18 grid[r][c] = '0';
19 Queue<int[]> queue = new Queue<int[]>();
20 queue.Enqueue(new int[] {r, c});
21 while (queue.Count > 0) {
22 int[] cell = queue.Dequeue();
23 foreach (int[] d in directions) {
24 int nr = cell[0] + d[0], nc = cell[1] + d[1];
25 if (nr >= 0 && nr < grid.Length && nc >= 0 && nc < grid[0].Length && grid[nr][nc] == '1') {
26 queue.Enqueue(new int[] {nr, nc});
27 grid[nr][nc] = '0';
28 }
29 }
30 }
31 }
32 }
33 }
34 return numIslands;
35 }
36}C# employs a Queue to facilitate BFS exploration over the grid. For each '1' found, BFS iteratively processes nodes by marking discovered ones and queueing adjacent '1's to ensure the whole island is traversed.