Programa C++ para encontrar todos los rectángulos rellenos con 0

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *