The Number of Islands problem is a classic algorithmic problem that asks you to count the number of disconnected “islands” in a grid of 1’s and 0’s. Here is an example of how to solve this problem in Python using a Depth-First Search (DFS) algorithm:

```
def numIslands(grid):
if not grid:
return 0
def dfs(grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '0'
dfs(grid, i+1, j)
dfs(grid, i-1, j)
dfs(grid, i, j+1)
dfs(grid, i, j-1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
```

In this solution, we use a nested function `dfs`

to perform a Depth-First Search algorithm on the input grid. The function takes the grid and two indices `i`

and `j`

as input. It first checks if the indices are out of bounds or if the current element is ‘0’. If either of these conditions is true, the function returns without doing anything.

If the current element is ‘1’, the function marks the current element as visited by changing it to ‘0’. Then, it recursively calls itself with each adjacent element in the grid, continuing the DFS until all connected elements have been marked as visited.

In the main function, we iterate through each element in the grid and call `dfs`

on each ‘1’ element we find. Each time we start a new DFS, we increment the `count`

variable, which keeps track of the total number of disconnected islands we have found.

To use this function, simply call `numIslands(grid)`

with the appropriate input grid `grid`

. The function will return the number of disconnected islands in the grid.

## + There are no comments

Add yours