count_island

count_island.py

class Ocean:
    def __init__(self, size):
        self.board = [None] * (size * size)
        self.size = size
        self.cnt = 0
        
    def find(self, a):
        return self.board[a] = find(self.board[a])
    
    def union(self, a, b) -> bool:
        a_parent = self.find(a)
        b_parent = self.find(b)
        if a_parent != b_parent:
            self.board[b] = a_parent
            return True
        return False
        
    def place_island(self, y, x) -> bool:
        self.cnt += 1
        index = y * self.size + x
        if self.board[index] == 0:
            self.board[index] = -1
            for r, c in ((y+1, x), (y-1, x), (y, x+1), (y, x-1)):
                if 0 <= y < self.size and 0 <= x < self.size:
                    neighbor = r * self.size + c
                    if self.board[neighbor] != 0:
                        if self.union(index, neighbor):
                            self.cnt -= 1
            return True
        else:
            return False
        
    def cnt_islands(self):
        return self.cnt
    
o = Ocean(3)
o.place_island(0, 0)
print(o.board)
o.place_island(1, 1)
print(o.board)
print(o.cnt_islands())
o.place_island(0, 1)
print(o.board)
print(o.cnt_islands())
o.place_island(2, 2)

# 
# Your previous Plain Text content is preserved below:
# 
# Let's consider a 2-d array (I'll refer to it as the ocean)
# 
# I'd like to implement two operations:
# 
# place_island(x, y) -> puts a landmass at (x, y)
# count_islands() -> returns the total number of connected landmasses
# 
# for example:
# 
# 111
# 100 -> count_islands() = 1
# 111
#