Tenemos una array 2D, llena de ceros y unos. Tenemos que encontrar el punto inicial y el punto final de todos los rectángulos rellenos con 0. Se sabe que los rectángulos están separados y no se tocan entre sí, sin embargo, pueden tocar el límite de la array. Un rectángulo puede contener solo un elemento.
Ejemplos:
input = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
Output:
[
[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]
]
Explanation:
We have three rectangles here, starting from
(2, 3), (3, 1), (5, 3)
Input = [
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 0]
]
Output:
[
[0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5],
[3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2],
[7, 6, 7, 6]
]
Paso 1: busque el 0 en filas y columnas
Paso 2: cuando encuentre cualquier 0, guarde su posición en la array de salida y use el cambio de bucle para cambiar todos los 0 relacionados con esta posición en cualquier número común para que podamos excluirlo de procesando la próxima vez.
Paso 3: cuando cambie todos los 0 relacionados en el Paso 2, almacene la ubicación de los últimos 0 procesados en la array de salida en el mismo índice.
Paso 4: Tenga especial cuidado cuando toque el borde, al no restar -1 porque el bucle se ha roto en la ubicación exacta.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to find all # rectangles filled with 0 def findend(i,j,a,output,index): x = len(a) y = len(a[0]) # flag to check column edge case, # initializing with 0 flagc = 0 # flag to check row edge case, # initializing with 0 flagr = 0 for m in range(i,x): # loop breaks where first 1 encounters if a[m][j] == 1: flagr = 1 # set the flag break # pass because already processed if a[m][j] == 5: pass for n in range(j, y): # loop breaks where first 1 encounters if a[m][n] == 1: flagc = 1 # set the flag break # fill rectangle elements with any # number so that we can exclude # next time a[m][n] = 5 if flagr == 1: output[index].append( m-1) else: # when end point touch the boundary output[index].append(m) if flagc == 1: output[index].append(n-1) else: # when end point touch the boundary output[index].append(n) def get_rectangle_coordinates(a): # retrieving the column size of array size_of_array = len(a) # output array where we are going # to store our output output = [] # It will be used for storing start # and end location in the same index index = -1 for i in range(0,size_of_array): for j in range(0, len(a[0])): if a[i][j] == 0: # storing initial position # of rectangle output.append([i, j]) # will be used for the # last position index = index + 1 findend(i, j, a, output, index) print (output) # driver code tests = [ [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1] ] get_rectangle_coordinates(tests)
Producción:
[[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]]
Complejidad temporal: O(x*y).
Espacio Auxiliar: O(x*y).
Consulte el artículo completo sobre Buscar todos los rectángulos rellenos con 0 para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA