number of islands in a bitmap

bitmap.py

# initial island map
bitmap = [
    [0,0,1,1,0,0,0,1,0,0],
    [0,1,1,0,0,1,1,1,0,0],
    [0,1,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,0,0,1,1],
    [0,0,0,0,1,1,1,1,1,0],
    [0,1,1,0,0,0,0,0,0,0]
]

# get size and initialize count
count = 0
height = len(bitmap)
width = len(bitmap[0])

# create an empty copy of the grid with all Falses
# we will use this to keep track of which nodes we have already
# visited (and therefore, which islands we have already counted)
visited = [[False]*width for x in range(0, height)]

# this recursive function looks at all surrounding up, down, left, right
# tiles and tries to visit them if they contain a land
# (this algorithm is known as "FloodFill")
def visitAll(x, y):
    # base case: we're at a water cell, or we've already visited this cell
    if not bitmap[x][y] or visited[x][y]:
        return
    # mark this cell as seen in our visited grid, so we know for later
    visited[x][y] = True
    
    # go through up, down, left, and right cells (abs(i) != abs(j)) means we won't hit
    # any of the diagonals, nor the center
    for i in range(-1, 2):
        for j in range(-1, 2):
            # also make sure that the new coordinate is actually in bounds
            # on the grid (not less than 0 or greater than width/height)
            if abs(i) != abs(j) and x+i>=0 and y+j>=0 and x+i<height and y+j<width:
                visitAll(x+i, y+j)

# go through all cells in the grid and attempt to visit them
# this will take O(N^2) runtime, but it won't waste time going
# into any cells that we've already visited
for x in range(0, height):
    for y in range(0, width):
        # already visited this one at an earlier run (via the recursive
        # function above), so skip it
        if visited[x][y]:
            continue
        
        # found a land cell! Increase our count, and mark its adjacent
        # cells as already visited as well
        if bitmap[x][y]:
            visitAll(x, y)
            count += 1

# print the total count, which only ever increased when we hit a "new"
# land cell. Since visitAll visited all the neighboring land cells (aka an
# island) and stopped us from double-counting any land cells, this value
# is also the total amount of islands.
print(count)

Hi sir, I went through the source code on your github. I've learned a lot, don't know if you've tried - Write a demo program using Python with algorithm Decryption using Frequency Analysis. Algorithm test link: https://www.101computing.net/frequency-analysis/ Vào Th 7, 2 thg 4, 2022 vào lúc 06:09 vgmoose ***@***.***> đã viết:

…

***@***.**** commented on this gist. ------------------------------ To view the above leetcode links, you may need to sign in. This is the similar question: https://leetcode.com/problems/number-of-islands/ — Reply to this email directly, view it on GitHub <https://gist.github.com/a15b7eab190abbf721ec#gistcomment-4118646>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AYMNUWDGZBJMIRIZH5B3HLLVC56ZFANCNFSM5SHL3A5Q> . You are receiving this because you commented.Message ID: <vgmoose/bitmap. ***@***.***>