Untitled
unknown
python
3 years ago
1.8 kB
4
Indexable
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))
Editor is loading...