Untitled

print("Islands")

test_grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"]
]
test_grid_2 = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

visited = set()
to_be_visited: [tuple] = [(0,0)]


def unvisited_adjacents(grid: [[str]], x: int, y: int) -> set:
    valids = set()
    if x - 1 >= 0 and (x - 1, y) not in visited:
        valids.add((x - 1, y))
    if x + 1 < len(grid) and (x + 1, y) not in visited:
        valids.add((x + 1, y))
    if y - 1 >= 0 and (x, y - 1) not in visited:
        valids.add((x, y - 1))
    if y + 1 < len(grid[0]) and (x, y + 1) not in visited:
        valids.add((x, y + 1))
    return valids

def explore_island(grid: [[str]], x: int, y: int) -> set:
    zeros = set()
    print("Explore island")
    visited.add((x, y))
    to_be_visited.extend(unvisited_adjacents(grid, x, y))

    while len(to_be_visited) > 0:
        (cur_x, cur_y) = to_be_visited.pop()
        if grid[cur_x][cur_y] == "1" and (cur_x, cur_y) not in visited:
            visited.add((cur_x, cur_y))
            to_be_visited.extend(unvisited_adjacents(grid, cur_x, cur_y))
        elif grid[cur_x][cur_y] == "0" and (cur_x, cur_y) not in visited:
            zeros.add((cur_x, cur_y))
    print(zeros)
    return zeros

def islands(grid: [[str]]) -> int:
    num_islands = 0
    while len(to_be_visited) > 0:
        (cur_x, cur_y) = to_be_visited.pop()
        if grid[cur_x][cur_y] == "1":
            print(f"Found island {cur_x} {cur_y}")
            to_be_visited.extend(explore_island(grid, cur_x, cur_y))
            num_islands += 1
        else:
            visited.add((cur_x, cur_y))
            to_be_visited.extend(unvisited_adjacents(grid, cur_x, cur_y))
    return num_islands


print(islands(test_grid_2))