我需要找到彼此相鄰的最大零序列（左上右下）。例如在這個例子中，函式應該回傳 6
mat = [[1,**0**,**0**,3,0],
[**0**,**0**,2,3,0],
[2,**0**,**0**,2,0],
[0,1,2,3,3],]
我標記為粗體的零應該是答案（6）解決方案應該在沒有任何回圈的情況下實作（使用遞回）
這是我到目前為止嘗試過的
def question_3_b(some_list,index_cord):
y = index_cord[0]
x = index_cord[1]
list_of_nums = []
def main(some_list,index_cord):
y = index_cord[0]
x = index_cord[1]
def check_right(x,y):
if x 1 < 0:
return 0
if some_list[y][x 1] == 0:
main(some_list,(y,x 1))
else:
return 0
def check_left(x,y):
if x -1 < 0:
return 0
if some_list[y][x - 1] == 0:
main(some_list,(y, x - 1))
def check_down(x,y):
if y 1 < 0:
return 0
try:
if some_list[y 1][x] == 0:
main(some_list,(y 1, x))
except:
print("out of range")
def check_up(x,y):
counter_up = 0
if y - 1 < 0:
return 0
if some_list[y - 1][x] == 0:
counter_up = 1
main(some_list,(y - 1, x))
list_of_nums.append((x,y))
right = check_right(x,y)
down = check_down(x,y)
left = check_left(x,y)
up = check_up(x, y)
main(some_list,index_cord)
print(list_of_nums)
question_3_b(mat,(0,1))
uj5u.com熱心網友回復：
解決方案 #1：經典 BFS
正如我在評論中提到的，你可以使用 BFS（廣度優先搜索）來解決這個問題，它會是這樣的：
# This function will give the valid adjacent positions
# of a given position according the matrix size (NxM)
def valid_adj(i, j, N, M):
adjs = [[i 1, j], [i - 1, j], [i, j 1], [i, j - 1]]
for a_i, a_j in adjs:
if 0 <= a_i < N and 0 <= a_j < M:
yield a_i, a_j
def biggest_zero_chunk(mat):
answer = 0
N, M = len(mat), len(mat[0])
# Mark all non zero position as visited (we are not instrested in them)
mask = [[mat[i][j] != 0 for j in range(M)] for i in range(N)]
queue = []
for i in range(N):
for j in range(M):
if mask[i][j]: # You have visited this position
continue
# Here comes the BFS
# It visits all the adjacent zeros recursively,
# count them and mark them as visited
current_ans = 1
queue = [[i,j]]
while queue:
pos_i, pos_j = queue.pop(0)
mask[pos_i][pos_j] = True
for a_i, a_j in valid_adj(pos_i, pos_j, N, M):
if mat[a_i][a_j] == 0 and not mask[a_i][a_j]:
queue.append([a_i, a_j])
current_ans = 1
answer = max(answer, current_ans)
return answer
mat = [[1,0,0,3,0],
[0,0,2,3,0],
[2,0,0,2,0],
[0,1,2,3,3],]
mat2 = [[1,0,0,3,0],
[0,0,2,3,0],
[2,0,0,0,0], # A slight modification in this row to connect two chunks
[0,1,2,3,3],]
print(biggest_zero_chunk(mat))
print(biggest_zero_chunk(mat2))
輸出：
6
10
解決方案 #2：僅使用遞回（無for陳述句）
def count_zeros(mat, i, j, N, M):
# Base case
# Don't search zero chunks if invalid position or non zero values
if i < 0 or i >= N or j < 0 or j >= M or mat[i][j] != 0:
return 0
ans = 1 # To count the current zero we start at 1
mat[i][j] = 1 # To erase the current zero and don't count it again
ans = count_zeros(mat, i - 1, j, N, M) # Up
ans = count_zeros(mat, i 1, j, N, M) # Down
ans = count_zeros(mat, i, j - 1, N, M) # Left
ans = count_zeros(mat, i, j 1, N, M) # Right
return ans
def biggest_zero_chunk(mat, i = 0, j = 0, current_ans = 0):
N, M = len(mat), len(mat[0])
# Base case (last position of mat)
if i == N - 1 and j == M - 1:
return current_ans
next_j = (j 1) % M # Move to next column, 0 if j is the last one
next_i = i 1 if next_j == 0 else i # Move to next row if j is 0
ans = count_zeros(mat, i, j, N, M) # Count zeros from this position
current_ans = max(ans, current_ans) # Update the current answer
return biggest_zero_chunk(mat, next_i, next_j, current_ans) # Check the rest of mat
mat = [[1,0,0,3,0],
[0,0,2,3,0],
[2,0,0,2,0],
[0,1,2,3,3],]
mat2 = [[1,0,0,3,0],
[0,0,2,3,0],
[2,0,0,0,0], # A slight modification in this row to connect two chunks
[0,1,2,3,3],]
print(biggest_zero_chunk(mat.copy()))
print(biggest_zero_chunk(mat2.copy()))
輸出：
6
10
筆記：
這個解決方案背后的思想仍然是 BFS（主要表現在count_zeros函式中）。此外，如果您有興趣在此之后使用矩陣值，您應該使用矩陣biggest_zero_chunk的副本呼叫 （因為它在演算法中進行了修改）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/473270.html
上一篇：改進遞回函式的除錯輸出