31.YA

def solution(grid: list) -> int:
    rows = len(grid)
    cols = len(grid[0])
    ans = 0
    seen = set()

    def validate(x, y):
        if x >= 0 and x < rows:
            if y >= 0 and y < cols:
                return True
        return False

    def dfs(row, col):
        stack = [(row, col)]
        while stack:
            x, y = stack.pop()

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if validate(x+dx, y+dy):
                    if grid[x+dx][y+dy] == '1' and (x+dx, y+dy) not in seen:
                        seen.add((x+dx, y+dy))
                        stack.append((x+dx, y+dy))

    for row in range(rows):
        for col in range(cols):
            # Нашли остров, который не посещали ранее
            if grid[row][col] == '1' and (row, col) not in seen:
                ans += 1
                seen.add((row, col))
                dfs(row, col)

    return ans