Encuentra 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 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++ 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.

# 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)

<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