只包含0和1的二维矩阵- python

Question

给定一个只包含0和1的二维矩阵。每个0代表陆地，每个1代表河流的一部分。一条河由任意数量的水平或垂直相邻(但不是对角线相邻)的15组成。形成一条河的相邻15的数目决定了它的大小。编写一个函数，返回输入矩阵中所有河流大小的数组。

Input:
array =[
[0, 0, 1, 0, 1, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1],
]
output:
There are 4 rivers in the given matrix, and their sizes are: [1, 3, 3, 4]

，但实际上我希望有:[1,2,2,2,3,3]

因为我只寻找水平或垂直相邻的河流，而不是两者都相邻的河流。(我的算法输出)。

MY算法使用DFS:

def riverSizes(matrix):
sizes = []  # # It would contain all of our river sizes
visited = [[False for value in row] for row in matrix]
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if visited[i][j]:
continue
traverseNode(i, j, matrix, visited, sizes)
return sizes

def traverseNode(i, j, matrix, visited, sizes):
currentRiverSize = 0
nodesToExplore = [[i, j]]
while len(nodesToExplore):
currentNode = nodesToExplore.pop()
i = currentNode[0]
j = currentNode[1]
if visited[i][j]:
continue
visited[i][j] = True
if matrix[i][j] == 0:
continue
currentRiverSize += 1
unvisitedNeighbors = getUnvisitedNeighbors(i, j, matrix, visited)
for neighbor in unvisitedNeighbors:
nodesToExplore.append(neighbor)
if currentRiverSize > 0:
sizes.append(currentRiverSize)

def getUnvisitedNeighbors(i, j, matrix, visited):
unvisitedNeighbors = []
if i > 0 and not visited[i - 1][j]:
unvisitedNeighbors.append([i - 1, j])
if i < len(matrix) - 1 and not visited[i + 1][j]:
unvisitedNeighbors.append([i + 1, j])
if j > 0 and not visited[i][j - 1]:
unvisitedNeighbors.append([i, j - 1])
if j < len(matrix[0]) - 1 and not visited[i][j + 1]:
unvisitedNeighbors.append([i, j + 1])
return unvisitedNeighbors

我该如何修复它?

Answer 1

该算法为问题[1, 3, 3, 4]提供了正确的结果。
一条河由水平或垂直相邻的1组成(1不能同时水平和垂直相邻于另一个1，在这种情况下混淆是问题陈述的'要么'或')。

这就是为什么getUnvisitedNeighbors()从包含1的场中观察所有垂直和水平方向的原因。
换句话说，一条河流可能有一个L形的结果矩阵