Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
counting connected components solution in Clear category for Boundary Blocks by David_Jones
def count_components(n, m, blocks):
def neighbors(cell):
(x,y) = cell
for (i,j) in ((x-1,y), (x+1,y), (x,y-1), (x,y+1)):
if 0 <= i < n and 0 <= j < m:
yield (i,j)
def visit(cell):
visited.add(cell)
for neighbor in neighbors(cell):
if neighbor not in blocks and neighbor not in visited:
visit(neighbor)
components = 0
visited = set()
for x in range(n):
for y in range(m):
if (x,y) not in blocks and (x,y) not in visited:
visit((x,y))
components += 1
return components
def boundary_blocks(grid):
n, m = len(grid), len(grid[0])
blocks = {(x,y) for x in range(n) for y in range(m) if grid[x][y] == 'X'}
components = count_components(n, m, blocks)
for block in blocks:
blocks.remove(block)
if count_components(n, m, blocks) < components:
yield block
blocks.add(block)
June 5, 2019