50 lines
1.1 KiB
Python
50 lines
1.1 KiB
Python
|
|
||
|
|
grid = [
|
||
|
|
[0,0,0,0,1],
|
||
|
|
[0,0,1,0,1],
|
||
|
|
[0,0,1,1,1],
|
||
|
|
[1,0,0,0,1],
|
||
|
|
[0,0,0,0,0]
|
||
|
|
]
|
||
|
|
|
||
|
|
blob_count = 1
|
||
|
|
|
||
|
|
for idx,i in enumerate(grid):
|
||
|
|
for jdx,j in enumerate(i):
|
||
|
|
print(grid[idx][jdx],end=' ')
|
||
|
|
print()
|
||
|
|
|
||
|
|
def is_valid(x,y):
|
||
|
|
return 0 <= x < rows and 0 <= y < cols and not visited[x][y] and grid[x][y] == '1'
|
||
|
|
|
||
|
|
rows,cols = len(grid), len(grid[0])
|
||
|
|
visited = [[False for _ in range(cols)] for _ in range(rows)]
|
||
|
|
directions = [(0,1),(0,-1),(1,0),(-1,0)]
|
||
|
|
|
||
|
|
def dfs(x, y,blob_count):
|
||
|
|
print(blob_count)
|
||
|
|
visited[x][y] = True
|
||
|
|
for dx, dy in directions:
|
||
|
|
nx, ny = x + dx, y + dy
|
||
|
|
|
||
|
|
if is_valid(nx, ny):
|
||
|
|
|
||
|
|
dfs(nx, ny,blob_count)
|
||
|
|
else:
|
||
|
|
blob_count += 1
|
||
|
|
return blob_count
|
||
|
|
|
||
|
|
|
||
|
|
for i in range(rows):
|
||
|
|
for j in range(cols):
|
||
|
|
if grid[i][j] == 1 and not visited[i][j]:
|
||
|
|
grid[i][j] = blob_count
|
||
|
|
blob_count = dfs(i, j,blob_count)
|
||
|
|
|
||
|
|
|
||
|
|
print(blob_count)
|
||
|
|
|
||
|
|
for idx,i in enumerate(grid):
|
||
|
|
for jdx,j in enumerate(i):
|
||
|
|
print(grid[idx][jdx],end=' ')
|
||
|
|
print()
|