#!/usr/bin/python3
# ===============================================================
# number of islands
#
# Given a m x n 2D grid which represents a map of '1's (land)
# and '0's (water). An island is surrounded by water and is
# formed by connecting adjacent lands horizontally or
# vertically. You may assume all four edges of the grid are
# surrounded by water.
# ===============================================================
grid1 = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
grid2 = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
def number_of_islands(grid):
def _dfs(grid,row,col):
# ---- base cases
if row < 0 or row > len(grid)-1 or \
col < 0 or col > len(grid[row])-1 or \
grid[row][col] == "0":
return 0
# ---- grid[row][col] is in the grid and not "0"
grid[row][col] = "0"
_dfs(grid,row+1,col)
_dfs(grid,row-1,col)
_dfs(grid,row,col+1)
_dfs(grid,row,col-1)
return 1
# ---- number_of_islands function main
count = 0
for row in range(len(grid)):
for col in range(len(grid[row])):
if grid[row][col] == "1":
count = count + _dfs(grid,row,col)
return count
# ----------------------------------------------------
# ---- main
# ----------------------------------------------------
n = number_of_islands(grid1)
print()
print(f'grid #1 number of islands {n}')
n = number_of_islands(grid2)
print()
print(f'grid #2 number of islands {n}')
print()