Skip to content

Instantly share code, notes, and snippets.

@gfnord
Last active June 10, 2021 21:39
Show Gist options
  • Save gfnord/60716b269ef389bbeeefe74d51512b84 to your computer and use it in GitHub Desktop.
Save gfnord/60716b269ef389bbeeefe74d51512b84 to your computer and use it in GitHub Desktop.
search islands 2d array
def count_islands(input):
# if there is no input, return 0
if not input:
return 0
# get the size of the array
row = len(input)
col = len(input[0])
count = 0
#print(row)
#print(col)
for i in range(row):
for j in range(col):
if input[i][j] == 1:
dfs(input, row, col, i, j)
count += 1
return count
def dfs(input, row, col, x, y):
if input[x][y] == 0:
return
# visited
input[x][y] = 0
# check the positions left, right, down and up
if x != 0:
dfs(input, row, col, x-1, y)
if x != row - 1:
dfs(input, row, col, x+1, y)
if y != 0:
dfs(input, row, col, x, y-1)
if y != col - 1:
dfs(input, row, col, x, y+1)
input1 = [[1,1,1,1,0],
[1,1,0,1,0],
[1,1,0,0,0],
[0,0,0,0,1]]
print(count_islands(input1))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment