Last active
August 13, 2020 16:17
-
-
Save acibiber53/a8583f69cba0639d87737101bc95802f to your computer and use it in GitHub Desktop.
Number of Islands question recursive DFS solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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