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.
1#include <vector>
2#include <queue>
3using namespace std;
4
5void bfs(vector<vector<char>>& grid, int r, int c) {
6 queue<pair<int, int>> q;
7 q.push({r, c});
8 grid[r][c] = '0';
9 vector<vector<int>> directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
10 while (!q.empty()) {
11 int cr = q.front().first;
12 int cc = q.front().second;
13 q.pop();
14 for (vector<int>& dir : directions) {
15 int nr = cr + dir[0], nc = cc + dir[1];
16 if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] == '1') {
17 grid[nr][nc] = '0';
18 q.push({nr, nc});
19 }
20 }
21 }
22}
23
24int numIslands(vector<vector<char>>& grid) {
25 int numIslands = 0;
26 for (int i = 0; i < grid.size(); i++) {
27 for (int j = 0; j < grid[i].size(); j++) {
28 if (grid[i][j] == '1') {
29 bfs(grid, i, j);
30 numIslands++;
31 }
32 }
33 }
34 return numIslands;
35}The C++ solution employs a std::queue to facilitate BFS over '1's in the grid. When a '1' is encountered, we launch BFS, exploring all connected '1's by marking them and enqueuing adjacent unvisited ones, effectively dedicating BFS for the whole discovered island.