Encuentre la longitud de ruta máxima en una array binaria

Dada una array cuadrada, cada elemento de la cual es 0 o 1 . Un valor 1 significa conectado y 0 significa no conectado. La tarea es encontrar la mayor longitud de un camino en la array después de cambiar al menos un 0 a 1 . Un camino es un grupo de 1 conectados en 4 direcciones.

Ejemplos:

Entrada: mat[][] = {{1, 1}, {1, 0}}
Salida: 4
Cambie el único 0 a 1 y la longitud de la ruta más grande será 4.

Entrada: mat[][] = {{1, 1}, {1, 1}}
Salida: 4

Enfoque ingenuo: la idea es cambiar cada ‘0’ a ‘1’ uno por uno y hacer una búsqueda en profundidad primero para encontrar el tamaño de la ruta más grande.

Enfoque eficiente: en el enfoque ingenuo, hemos verificado cada ‘0’. Sin embargo, también podemos hacer que esto sea eficiente almacenando el tamaño de cada grupo, de modo que no tengamos que usar la búsqueda en profundidad para calcular repetidamente el mismo tamaño de nuevo.

Nota: debemos tener cuidado cuando el 0 toca el mismo grupo. Por ejemplo, considere cuadrícula = [[0, 1], [1, 1]]. El vecino derecho e inferior del 0 pertenecerá al mismo grupo después de cambiar 0 a 1 .

Podemos resolver este problema haciendo un seguimiento del ID de grupo (o índice ), que será único para cada grupo.

• Para cada grupo, llénelo con el índice de valor y recuerde su tamaño como un elemento en el área de array [Índice] que se puede encontrar con una búsqueda en profundidad.
• Luego, para cada 0 , mire los ID de grupos vecinos y agregue el área de esos grupos, y agregue 1 para el 0 que estamos alternando. Esto nos dará la respuesta, y tomamos el máximo de la respuesta anterior.

A continuación se muestra la implementación del enfoque anterior:

# Python3 implementation of above approach
  
# check if index is within range
def neighbors(r, c, N):
    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= nr < N and 0 <= nc < N:
            yield nr, nc
  
# dfs to calculate length of path
def dfs(R, C, index, grid, N):
    ans = 1
    grid[R][C] = index
    for nr, nc in neighbors(R, C, N):
        if grid[nr][nc] == 1:
            ans += dfs(nr, nc, index)
  
    return ans
  
  
# function to return largest possible length of Path
def largestPath(grid):
  
    N = len(grid)
  
    area = {}
    index = 2
  
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 1:
                area[index] = dfs(i, j, index, grid, N)
                index += 1
  
    ans = max(area.values() or [0])
  
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 0:
                seen = {grid[nr][nc] for nr, nc in neighbors(i, j, N) if grid[nr][nc] > 1}
                ans = max(ans, 1 + sum(area[i] for i in seen))
  
    # return maximum possible length
    return ans
  
# Driver code
I = [[1, 0], [0, 1]]
  
# Function call to print answer
print(largestPath(I))
  
# This code is written by
# Sanjit_Prasad

3