Skip to content

Instantly share code, notes, and snippets.

@acibiber53
Last active August 13, 2020 16:17
Show Gist options
  • Save acibiber53/a8583f69cba0639d87737101bc95802f to your computer and use it in GitHub Desktop.
Save acibiber53/a8583f69cba0639d87737101bc95802f to your computer and use it in GitHub Desktop.
Number of Islands question recursive DFS solution
class Solution:
def numIslands(self, grid):
# They have empty input
if not grid:
return 0
directions = {"up": (-1,0), "down":(1,0), "left":(0,-1), "right":(0,1)}
island_number = 0
lenx, leny = len(grid), len(grid[0])
def land_zeroizer(x, y):
# stop if out of bounds
if x<0 or y<0 or x>=lenx or y>=leny:
return
# stop if reached to the sea
if grid[x][y] == '0':
return
# Make every visited land into sea
grid[x][y] = '0'
# Go to each direction
for way in directions:
i,j = directions.get(way)
land_zeroizer(x+i,y+j)
# Check each tile
for i, row in enumerate(grid):
for j, land in enumerate(row):
if land == '0':
continue
# If it is a land, then we make everything connected to it into sea and increase island number by 1
land_zeroizer(i,j)
island_number +=1
return island_number
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment