Encuentre el número de rectángulos de esquina que se pueden formar a partir de Matrix dada

Dada una array binaria mat[][] de dimensiones N*M , la tarea es encontrar el número de rectángulos de esquina que se pueden formar. Un rectángulo de esquina se define como la subarray que tiene unos en las esquinas y cada uno debe pertenecer a una celda única en esa subarray .

Ejemplos:

Entrada: mat[][] = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}
Salida: 1
Explicación:
Solo existe una subarray que satisface la fórmula dada representada en negrita como:
1 0 1
0 0 0
1 0 1

Entrada: mat[][] = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}
Salida: 9

Enfoque: El problema dado se puede resolver usando los conceptos de todos los pares posibles distintos de N puntos que están dados por ^N C ₂ . La idea es almacenar la frecuencia del par de celdas (i, j) que tienen los valores como 1s en el mapa de pares , digamos M. Después de generar el mapa de frecuencia, encuentre el recuento total de esquinas del rectángulo formado con la fórmula anterior. Siga los pasos a continuación para resolver el problema dado:

• Inicialice una variable, digamos cuenta , que almacena la cuenta resultante del rectángulo de esquina.
• Inicialice un mapa , digamos m[] que almacena la frecuencia de la celda (i, j) que tiene valores como 1 .
• Itere sobre el rango [0, M) usando la variable i y realice las siguientes tareas:
  • Iterar sobre el rango [0, N) usando la variable j y si mat[i][j] es igual a 1 entonces Iterar sobre el rango [j_+1, N) usando la variable k y si el valor de mat[i][ k] es igual a 1 , luego aumente la cuenta de m[{j, k}] en 1.
• Recorra el mapa m[] usando la variable it y agregue el valor de it.second*(it.second – 1)/2 a la variable count.
• Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all possible rectangles
// having distinct corners as 1s
int countCornerRectangles(
    vector<vector<int> >& mat)
{
    // Stores the count of rectangles
    int count = 0;
 
    int N = mat.size();
    int M = mat[0].size();
 
    // Map to store the frequency
    map<pair<int, int>, int> m;
 
    // Iterate over each row
    for (int i = 0; i < N; i++) {
 
        // Iterate over each cell
        for (int j = 0; j < M; j++) {
            if (mat[i][j] == 1) {
 
                // Check for 1's of th
                // same column pair
                for (int k = j + 1;
                     k < M; k++) {
                    if (mat[i][k] == 1) {
                        m[{ j, k }]++;
                    }
                }
            }
        }
    }
 
    // For any pair of column cells (x, y)
    // If the frequency is n. Then choosing
    // any 2 will form a rectangle
    for (auto& it : m) {
        count
            += (it.second * (it.second - 1)) / 2;
    }
 
    return count;
}
 
// Driver Code
int main()
{
    vector<vector<int> > mat
        = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
 
    cout << countCornerRectangles(mat);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
import java.util.Map.Entry;
 
class GFG{
    static class pair
    {
        int first, second;
        public pair(int first, int second) 
        {
            this.first = first;
            this.second = second;
        }   
    }
   
// Function to find all possible rectangles
// having distinct corners as 1s
static int countCornerRectangles(int[][] mat)
{
   
    // Stores the count of rectangles
    int count = 0;
 
    int N = mat.length;
    int M = mat[0].length;
 
    // Map to store the frequency
    HashMap<pair, Integer> m = new HashMap<>();
 
    // Iterate over each row
    for (int i = 0; i < N; i++) {
 
        // Iterate over each cell
        for (int j = 0; j < M; j++) {
            if (mat[i][j] == 1) {
 
                // Check for 1's of th
                // same column pair
                for (int k = j + 1;
                     k < M; k++) {
                    if (mat[i][k] == 1) {
                        if(m.containsKey(new pair(j,k)))
                        m.put( new pair(j,k), m.get(new pair(j,k))+1);
                        else
                            m.put( new pair(j,k), 1);
                    }
                }
            }
        }
    }
 
    // For any pair of column cells (x, y)
    // If the frequency is n. Then choosing
    // any 2 will form a rectangle
    for (Entry<pair, Integer> it : m.entrySet()){
        count
            += (it.getValue() * (it.getValue()+1)) / 2;
    }
 
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int[][] mat
        = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
 
    System.out.print(countCornerRectangles(mat));
 
}
}
 
// This code is contributed by Rajput-Ji

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to find all possible rectangles
# having distinct corners as 1s
def countCornerRectangles(mat):
 
    # Stores the count of rectangles
    count = 0
 
    N = len(mat)
    M = len(mat[0])
 
    # Map to store the frequency
    m = defaultdict(int)
 
    # Iterate over each row
    for i in range(N):
 
        # Iterate over each cell
        for j in range(M):
            if (mat[i][j] == 1):
 
                # Check for 1's of th
                # same column pair
                for k in range(j + 1, M):
                    if (mat[i][k] == 1):
                        m[(j, k)] += 1
 
    # For any pair of column cells (x, y)
    # If the frequency is n. Then choosing
    # any 2 will form a rectangle
    for it in m:
        count += (m[it] * (m[it] - 1)) // 2
 
    return count
 
# Driver Code
if __name__ == "__main__":
 
    mat = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
 
    print(countCornerRectangles(mat))
 
    # This code is contributed by ukasp.

<script>
       // JavaScript code for the above approach
 
       // Function to find all possible rectangles
       // having distinct corners as 1s
       function countCornerRectangles(
           mat)
           {
           // Stores the count of rectangles
           let count = 0;
 
           let N = mat.length;
           let M = mat[0].length;
 
           // Map to store the frequency
           let m = new Map();
 
           // Iterate over each row
           for (let i = 0; i < N; i++) {
 
               // Iterate over each cell
               for (let j = 0; j < M; j++) {
                   if (mat[i][j] == 1) {
 
                       // Check for 1's of th
                       // same column pair
                       for (let k = j + 1;
                           k < M; k++) {
                           if (mat[i][k] == 1) {
                               if (m.has({ first: j, second: k }))
                                   m.set({ first: j, second: k }, m.get({ first: j, second: k }) + 1);
                               else
                                   m.set({ first: j, second: k }, 1)
                           }
                       }
                   }
               }
           }
 
           // For any pair of column cells (x, y)
           // If the frequency is n. Then choosing
           // any 2 will form a rectangle
           for (let val of m.values()) {
               count += ((val * (val - 1)) / 2) + 1;
           }
 
           return count;
       }
 
       // Driver Code
       let mat
           = [[1, 1, 1], [1, 1, 1], [1, 1, 1]];
 
       document.write(countCornerRectangles(mat));
 
      // This code is contributed by Potta Lokesh
   </script>

9

Complejidad de Tiempo: O(N*M ² )
Espacio Auxiliar: O(M ² )