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:
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.
Producción:
[[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]]
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