Я пробовал реализацию на python, которая использует алгоритмический подход DFS и работает со сложностью времени O (M x N).Входом для функции является список M * N.
rows, cols = 0, 0
# The main function that provides count of islands in a given M*N matrix
def traverse_dfs(A, directions, i, j, visited):
global rows, cols
# A function to check if a given cell (row, col) can be included in DFS
def isSafe(A, row, col, visited, current):
return ( row >=0 and row < rows and col >=0 and col < cols and \
not visited[row][col] and (current == A[row][col]))
visited[i][j] = True
# print i, j
# Recurrence for all connected neighbours
for k in range(len(directions)):
if isSafe(A, i+directions[k][0], j+directions[k][1], visited, A[i][j]):
traverse_dfs(A, directions, i+directions[k][0], j+directions[k][1], visited)
def countRegions(A):
global rows, cols
rows, cols = len(A), len(A[0])
print A
if(rows is 1 and cols is 1):
return 1
# Below list gives the possible directions in which we can move
directions = [[1, 0], [0, -1], [-1, 0], [0, 1]]
visited = []
# Make a bool array to mark visited cells, Initially all cells are unvisited
for i in range(rows):
l = []
for j in range(cols):
l.append(False)
visited.append(l)
count = 0
for i in range(rows):
for j in range(cols):
if not visited[i][j]:
traverse_dfs(A, directions, i, j, visited)
count += 1
print "Regions count: {0}".format(count)
[[5, 4, 4], [4, 3, 4], [3, 2, 4], [2, 2, 2], [3, 3, 4], [1, 4, 4], [4, 1, 1]]
Regions count: 11
[[2, 3, 3], [4, 4, 1], [2, 1, 1], [5, 2, 3], [5, 2, 2], [1, 4, 1], [3, 4, 1]]
Regions count: 12
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Regions count: 9
[[1, 1, 1], [2, 2, 2], [3, 3, 3]]
Regions count: 3
[[1, 1], [2, 2], [3, 3]]
Regions count: 3
[[1, 2], [1, 2]]
Regions count: 2
[[1, 2], [3, 4]]
Regions count: 4
[[1, 1], [1, 1]]
Regions count: 1
[[1], [2]]
Regions count: 2
[[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Regions count: 9