I need to find the biggest sequence of zeros next to each other (up down left right). for example in this example the function should return 6

mat = [[1,**0**,**0**,3,0],
       [**0**,**0**,2,3,0],
       [2,**0**,**0**,2,0],
       [0,1,2,3,3],]

the zeros that i marked as bold should be the answer (6) the solution should be implemented without any loop (using recursion)

this is what i tried so far

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))

CodePudding user response：

Solution #1: classic BFS

As I mention in a comment, you can tackle this problem using BFS (Breadth First Search), it will be something like this:

# 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))

Output:

6
10

Solution #2: using only recursion (no for statements)

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()))

Output:

6
10

Notes:

The idea behind this solution is still BFS (represented mainly in the count_zeros function). Also, if you are interested in using the matrix values after this you should call the biggest_zero_chunk with a copy of the matrix (because it is modified in the algorithm)