I’m writing an algorithm that detects regions of contiguous empty cells that are completely surrounded by filled cells and do not extend to the edge of the grid. Let’s call such regions “pools”.

As you can see in the below visualization, there are three pool cells, forming the one and only pool in the grid: (1, 1), (1, 3), and (2, 2).

I have already implemented an algorithm that partially solves the problem: it correctly identifies pool cells.

class Cell:
    x: int
    y: int
    is_filled: bool

    def __init__(self, x, y, is_filled):
        self.x = x
        self.y = y
        self.is_filled = is_filled

    def get_neighbor(self, grid, direction):
        if direction == "LEFT" and self.y > 0:
            return Cell(self.x, self.y - 1, grid[self.x][self.y - 1] == 1)
        if direction == "TOP" and self.x > 0:
            return Cell(self.x - 1, self.y, grid[self.x - 1][self.y] == 1)
        if direction == "RIGHT" and self.y < len(grid[0]) - 1:
            return Cell(self.x, self.y + 1, grid[self.x][self.y + 1] == 1)
        if direction == "BOTTOM" and self.x < len(grid) - 1:
            return Cell(self.x + 1, self.y, grid[self.x + 1][self.y] == 1)
        return None

def iterate_pool_cells(grid):
    def is_pool(cell, is_edge):
        if cell is None:  # Reached grid boundary, not a pool
            is_edge["reached"] = True
            return False
        if (cell.x, cell.y) in visited or cell.is_filled:  # Already visited or is land
            return True
        visited.add((cell.x, cell.y))  # Mark as visited
        is_enclosed = True
        is_enclosed = is_pool(cell.get_neighbor(grid, "LEFT"), is_edge) and is_enclosed
        is_enclosed = is_pool(cell.get_neighbor(grid, "TOP"), is_edge) and is_enclosed
        is_enclosed = is_pool(cell.get_neighbor(grid, "RIGHT"), is_edge) and is_enclosed
        is_enclosed = is_pool(cell.get_neighbor(grid, "BOTTOM"), is_edge) and is_enclosed
        return is_enclosed and not is_edge["reached"]

    visited = set()
    for x in range(len(grid)):
        for y in range(len(grid[0])):
            cell = Cell(x, y, grid[x][y] == 1)
            if (x, y) not in visited and not cell.is_filled:
                is_edge = {"reached": False}
                if is_pool(cell, is_edge) and not is_edge["reached"]:
                    yield (x, y)

The problem lies in the second half of the algorithm, i.e. the iterator. I am aiming to only yield cells that start a pool, (i.e. only the top-left cell in a given pool). However, since right now diagonal adjacency isn’t being taken into account, the iterator will yield all three of the cells from the example, even though they all belong to the same pool.

I’ve tried approaches with both modifying the iterator and the isPool function itself, but nothing has worked. The problem either remains or I end up getting false negatives on all the pool cells.

Can someone please steer me in the right direction on how to solve this?

Here’s a test case involving the grid from the image:

grid = [
  [ 0, 1, 0, 1, 0 ],
  [ 1, 0, 1, 0, 1 ],
  [ 1, 1, 0, 1, 1 ],
  [ 1, 0, 1, 0, 1 ],
  [ 0, 0, 1, 0, 0 ],
  [ 1, 0, 1, 0, 1 ],
]

for pool_cell in iterate_pool_cells(grid):
    print(f"Pool starts at cell: {pool_cell}")