Lakes in an island

count_lakes.py

# Water is represented by 0 and land is represented by 1.
input_grid = [
    [0,0,1,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,1,1,1,1,0,0,0,0,0,0,0,0],
    [0,1,0,0,1,1,0,0,1,1,1,0,0],
    [0,1,0,1,1,1,0,0,1,1,1,0,0],
    [0,0,1,0,0,0,0,0,1,0,1,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,0,0,0,0,0,0,1,1,0,0,0,0]
]

# Given an entire grid and a point coordinate, return the island coordinates
def getIslandCoordinates(grid, start_coordinate):
    def BFS(i, j):
        queue = [(i, j)]
        while queue:
            i, j = queue.pop(0)
            for direction in directions:
                ni, nj = i + direction[0], j + direction[1]
                if ni >= 0 and nj >= 0 and ni < len(grid) and nj < len(grid[0]) and grid[ni][nj] == 1 and (ni, nj) not in island_coordinates:
                    island_coordinates.add((ni, nj))
                    queue.append((ni, nj))

    # move in 8 directions to build the land coordinates
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    island_coordinates = set([start_coordinate])
    BFS(*start_coordinate)    
    
    # build the island matrix
    min_i = min(coordinate[0] for coordinate in island_coordinates)
    max_i = max(coordinate[0] for coordinate in island_coordinates)
    min_j = min(coordinate[1] for coordinate in island_coordinates)
    max_j = max(coordinate[1] for coordinate in island_coordinates)

    island_matrix = [[0]*(max_j-min_j+1) for _ in range(max_i-min_i+1)]
    for coordinate in island_coordinates:
        island_matrix[coordinate[0]-min_i][coordinate[1]-min_j] = 1

    return island_matrix

# Given an island matrix, count the number of lakes
def countNumberOfLakes(island_matrix):
    def DFS(i, j, visited):
        if i < 0 or j < 0 or i >= len(island_matrix) or j >= len(island_matrix[0]) or island_matrix[i][j] != 0 or (i, j) in visited:
            return
        visited.add((i, j))
        for direction in directions:
            ni, nj = i + direction[0], j + direction[1]
            DFS(ni, nj, visited)

    # move in 4 directions to count the number of lakes
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    lakes = 0
    visited = set()
    # lake cannot be on the border, so start from 1 to len-1
    for i in range(1, len(island_matrix)-1):
        for j in range(1, len(island_matrix[0])-1):
            if island_matrix[i][j] == 0 and (i, j) not in visited:
                DFS(i, j, visited)
                lakes += 1
    return lakes

for coord in [(0, 7), (2, 2), (3, 8)]:
    if input_grid[coord[0]][coord[1]] == 1:
        island_matrix = getIslandCoordinates(input_grid, coord)
        num_lakes = countNumberOfLakes(island_matrix)
        print(num_lakes)