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 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:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; void findend(int i,int j, vector<vector<int>> &a, vector<vector<int>> &output,int index) { int x = a.size(); int y = a[0].size(); // flag to check column edge case, // initializing with 0 int flagc = 0; // flag to check row edge case, // initializing with 0 int flagr = 0; int n, m; for (m = i; m < x; m++) { // 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) continue; for (n = j; n < y; n++) { // 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].push_back(m-1); else // when end point touch the boundary output[index].push_back(m); if (flagc == 1) output[index].push_back(n-1); else // when end point touch the boundary output[index].push_back(n); } void get_rectangle_coordinates(vector<vector<int>> a) { // retrieving the column size of array int size_of_array = a.size(); // output array where we are going // to store our output vector<vector<int>> output; // It will be used for storing start // and end location in the same index int index = -1; for (int i = 0; i < size_of_array; i++) { for (int j = 0; j < a[0].size(); j++) { if (a[i][j] == 0) { // storing initial position // of rectangle output.push_back({i, j}); // will be used for the // last position index = index + 1; findend(i, j, a, output, index); } } } cout << "["; int aa = 2, bb = 0; for(auto i:output) { bb = 3; cout << "["; for(int j:i) { if(bb) cout << j << ", "; else cout << j; bb--; } cout << "]"; if(aa) cout << ", "; aa--; } cout << "]"; } // Driver code int main() { vector<vector<int>> 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); return 0; } // This code is contributed by mohit kumar 29.
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)
Javascript
<script> // JavaScript program to find all // rectangles filled with 0 function findend(i,j,a,output,index){ let x = a.length let y = a[0].length let m,n; // flag to check column edge case, // initializing with 0 let flagc = 0 // flag to check row edge case, // initializing with 0 let flagr = 0 for(m=i;m<x;m++){ // 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=j;n<y;n++){ // 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].push( m-1) else // when end point touch the boundary output[index].push(m) if(flagc == 1) output[index].push(n-1) else // when end point touch the boundary output[index].push(n) } function get_rectangle_coordinates(a){ // retrieving the column size of array let size_of_array = a.length // output array where we are going // to store our output let output = [] // It will be used for storing start // and end location in the same index let index = -1 for(let i=0;i<size_of_array;i++){ for(let j=0;j<a[0].length;j++){ if(a[i][j] == 0){ // storing initial position // of rectangle output.push([i, j]) // will be used for the // last position index = index + 1 findend(i, j, a, output, index) } } } console.log(output) } // driver code let 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) // This code is contributed by shinjanpatra </script>
[[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]]
Complejidad temporal: O(x*y).
Espacio Auxiliar: O(x*y).
Este artículo es una contribución de Prabhat jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Preguntado en Intuit
Publicación traducida automáticamente
Artículo escrito por Prabhat jha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA