Skip to content

Instantly share code, notes, and snippets.

@jayceazua

jayceazua/island_count.py

Last active November 20, 2019 18:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jayceazua/99665fb229d556ccdcbf56925cfda544 to your computer and use it in GitHub Desktop.
Save jayceazua/99665fb229d556ccdcbf56925cfda544 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
island_count.py
def island_count(grid):
if not grid:
return 0
nr = len(grid)
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == ‘1’:
num_islands += 1
# convert the island into water
dfs(grid, r, c)
return num_islands
def dfs(grid, r, c):
nr = len(grid)
nc = len(grid[0])
# check for bounds and check if it is water
if r < 0 or r >= nr or c < 0 or c >= nc or grid[r][c] == ‘0’:
return
grid[r][c] = ‘0’
dfs(grid, r - 1, c)
dfs(grid, r + 1, c)
dfs(grid, r, c - 1)
dfs(grid, r, c + 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment