我需要在2d矩阵中递归地找到0的最长路径，不知道怎么做。(对于给定的(i, j)，它只能向上、向下、向右或向左移动)
例如这个矩阵:
mat = [[1, 0, 0, 3, 0],
[0, 0, 2, 3, 0],
[2, 0, 0, 2, 0],
[0, 1, 2, 3, 3]]
print(question3_b(mat))
这应该返回6，因为有大小为1,3,6的社区。我的尝试:我创建了一些包装函数来查找列表中的最大值，以及一个函数来查找给定(I,j)元素的路由并将其添加到列表中，并在矩阵中的每个点(I,j)上执行此操作。
def question3_b(mat) -> int:
rows: int = len(mat)
cols: int = len(mat[0])
community_lengths = list()
for i in range(rows):
for j in range(cols):
visited = zeros(rows, cols) # create a 2d list of 0's with size rows,cols
a = findcommunity(mat, (i, j), visited)
print("a=", a)
community_lengths.append(a)
print(community_lengths)
return findmax(community_lengths)
def findcommunity(mat: list, indices: tuple, visited: list): # find length of community
#global rec_counter
#rec_counter += 1
i, j = indices
rows = len(mat)
cols = len(mat[0])
if mat[i][j] == 0:
visited[i][j] = 1
if i < rows - 1:
if visited[i + 1][j] == 0:
return 1 + findcommunity(mat, (i + 1, j), visited)
if j < cols - 1:
if visited[i][j + 1] == 0:
return 1 + findcommunity(mat, (i, j + 1), visited)
if i > 0:
if visited[i - 1][j] == 0:
return 1 + findcommunity(mat, (i - 1, j), visited)
if j > 0:
if visited[i][j - 1] == 0:
return 1 + findcommunity(mat, (i, j - 1), visited)
else: # mat[i][j]!=0
return 0
def zeros(rows:int,cols:int)->list: #create a 2d matrix of zeros with size (rows,cols)
if rows==1 and cols==1:return [[0]]
if rows==1 and cols>1:return [[0]*cols]
if rows>1 and cols>1:return zeros(rows-1,cols)+zeros(1,cols)
def findmax(arr:list)->int: # find max in an array using recursion
if len(arr)==2:
if arr[0]>arr[1]:return arr[0]
else:return arr[1]
else:
if arr[0]>arr[1]:
arr[1]=arr[0]
return findmax(arr[1:])
else:
return findmax(arr[1:])
我哪里做错了?对于一个4X4个0的矩阵，我希望它运行16*16次[每个I,j 16次，矩阵中有16个元素]。但它只运行一次。0是一个递归函数，我让它像np一样。0，它创建一个2d矩阵，里面全是指定大小的0。
它真的很乱，但我试图只是改变你的代码，而不是写一个新的解决方案。你应该看看collections deque。我见过好几次这样的情况，人们更容易跟踪visited。
我将visit改为循环外，并使用np.zeros定义它(没有您的函数;))。我不确定你在返回时的递归函数调用是否错误，但你的if语句是错误的，或者至少是它背后的逻辑(或者我不理解，也可能:))我完全改变了那个街区。第一次在mat中遇到0时，递归部分将挖掘mat，只要它在它的左边，右边，底部或顶部找到另一个0(这是dc和dr背后的功能)。这就是community_counter增加的地方。如果函数返回最后一次，并且您跳到question_3b的外循环，计数器将被重置并搜索下一个0(另一个社区的下一个开始)。
import numpy as np
def question3_b(mat) -> int:
rows: int = len(mat)
cols: int = len(mat[0])
community_lengths = list()
visited = np.zeros((rows, cols)) # create a 2d list of 0's with size rows,cols
community_count = 0
for row in range(rows):
for col in range(cols):
if visited[row][col]==0:
community_count,visited = findcommunity(mat, (row, col), visited, community_count)
if community_count!=0:
community_lengths.append(community_count)
community_count=0
return community_lengths
def findcommunity(mat: list, indices: tuple, visited: list,community_count: int): # find length of community
i, j = indices
rows = len(mat)
cols = len(mat[0])
visited[i][j] = 1
if mat[i][j] == 0:
community_count += 1
dr = [-1, 0, 1, 0]
dc = [0,-1, 0, 1]
for k in range(4):
rr = i + dr[k]
cc = j + dc[k]
if 0<=rr<rows and 0<=cc<cols:
if visited[rr][cc]==0 and mat[rr][cc]==0:
community_count, visited = findcommunity(mat, (rr,cc), visited, community_count)
return community_count,visited
else:
return community_count,visited
mat = [[1, 0, 0, 3, 0],
[0, 0, 2, 3, 0],
[2, 0, 0, 2, 0],
[0, 1, 2, 3, 3]]
all_communities = question3_b(mat)
print(all_communities)
# [6, 3, 1]
print(max(all_communities))
# 6
编辑
这是findcommunity函数在你的方式。测试过了，效果也不错。
def findcommunity(mat: list, indices: tuple, visited: list,community_count: int): # find length of community
i, j = indices
rows = len(mat)
cols = len(mat[0])
visited[i][j] = 1
if mat[i][j] == 0:
community_count += 1
if i < rows - 1:
if visited[i + 1][j] == 0:
community_count, visited = findcommunity(mat, (i + 1, j), visited, community_count)
if j < cols - 1:
if visited[i][j + 1] == 0:
community_count, visited = findcommunity(mat, (i, j + 1), visited, community_count)
if i > 0:
if visited[i - 1][j] == 0:
community_count, visited = findcommunity(mat, (i - 1, j), visited, community_count)
if j > 0:
if visited[i][j - 1] == 0:
community_count, visited = findcommunity(mat, (i, j - 1), visited, community_count)
return community_count,visited
else:
return community_count,visited
这里有一个完全不同的方法，如果有人感兴趣的话。
import numpy as np
mat = [[1, 0, 0, 3, 0],
[0, 0, 2, 3, 0],
[2, 0, 0, 2, 0],
[0, 1, 2, 3, 3]]
mat = np.array(mat)
# some padding of -1 to prevent index error
mask = np.full(np.array(mat.shape) + 2, -1)
mask[1:-1, 1:-1 ] = mat
# visiteds are set to -2
def trace(f, pt):
mask[tuple(pt)], pts = -2, [pt - 1]
pts += [trace(f, pt + d) for d in
([0, 1], [1, 0], [0, -1], [-1, 0]) if
mask[tuple(pt + d)] == f]
return pts
clusters = lambda f: {tuple(pt-1): trace(f, pt) for pt in np.argwhere(mask==f) if mask[tuple(pt)]==f}
# now call with value your looking for
print(clusters(0))