Contar triángulos rectángulos en una array que tenga dos de sus lados paralelos a los lados de la array

Dada una array binaria arr[][] de dimensiones N * M , la tarea es contar el número de triángulos rectángulos que se pueden formar uniendo las celdas que contienen el valor 1 de manera que los triángulos deben tener dos de sus lados paralela a los lados del rectángulo.

Ejemplos:

Entrada: arr[][] = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}
Salida: 4
Explicación: Los triángulos rectángulos que se pueden formar son (a[ 1][1], a[1][0], a[0][1]), (a[1][1], a[2][1], a[1][0]), ( a[1][1], a[1][2], a[0][1]) y (a[1][1], a[1][2], a[2][1])

Entrada: arr[][] = {{1, 0, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}}
Salida : 16

Enfoque: La idea es atravesar la cuadrícula dada y almacenar el conteo de 1 s presente en cada fila y cada columna en arreglos auxiliares fila[] y col[] respectivamente. Luego, para cada celda en la cuadrícula arr[][] , si arr[i][j] es 1 , entonces el número total de triángulos rectángulos formados se puede calcular mediante (row[i] – 1)*(col[ j] – 1) para cada celda. Siga los pasos a continuación para resolver el problema:

• Inicialice las arrays col[] y row[] con 0 .
• Atraviesa la cuadrícula dada y visita cada celda arr[i][j] .
• Si arr[i][j] es 1 , incremente fila[i] y col[j] en 1 .
• Después de atravesar la cuadrícula, inicialice una variable ans con 0 .
• Recorra nuevamente toda la cuadrícula y ahora, si arr[i][j] es 1 , actualice la cuenta del triángulo rectángulo de la siguiente manera:

(fila[i] – 1)*(columna[j] – 1)

• Después de atravesar, imprima el valor de ans como el número total de triángulos rectángulos.

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 count the right-angled
// triangle in the given grid a[][]
int numberOfTriangle(
    vector<vector<int> >& a)
{
    int N = a.size();
    int M = a[0].size();
 
    // Stores the count of 1s for
    // each row[] and column[]
    int rows[N] = { 0 };
    int columns[M] = { 0 };
 
    // Find the number of 1s in
    // each of the rows[0, N - 1]
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // Increment row[i]
            if (a[i][j] == 1) {
                rows[i]++;
            }
        }
    }
 
    // Find the number of 1s in
    // each of the columns[0, N - 1]
    for (int i = 0; i < M; ++i) {
 
        for (int j = 0; j < N; ++j) {
 
            // Increment columns[i]
            if (a[j][i] == 1) {
                columns[i]++;
            }
        }
    }
 
    // Stores the count of triangles
    int answer = 0;
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // If current cell has value 1
            if (a[i][j] == 1) {
 
                // Update the answer
                answer += (rows[i] - 1)
                          * (columns[j] - 1);
            }
        }
 
        
    }
   // Return the count
        return answer;
}
 
 
// Driver Code
int main()
{
    // Given grid arr[][]
    vector<vector<int> > arr;
 
    arr = { { 1, 0, 1, 0 },
            { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 0, 1, 0, 1 } };
 
    // Function Call
    cout << numberOfTriangle(arr);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to count the right-angled
// triangle in the given grid a[][]
static int numberOfTriangle(int[][] a)
{
  int N = a.length;
  int M = a[0].length;
 
  // Stores the count of 1s for
  // each row[] and column[]
  int []rows = new int[N];
  int []columns = new int[M];
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < M; ++j)
    {
      // Increment row[i]
      if (a[i][j] == 1)
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for (int i = 0; i < M; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      // Increment columns[i]
      if (a[j][i] == 1)
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count
  // of triangles
  int answer = 0;
 
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; ++j)
    {
      // If current cell
      // has value 1
      if (a[i][j] == 1)
      {
        // Update the answer
        answer += (rows[i] - 1) *
                  (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given grid arr[][]
  int [][]arr = {{1, 0, 1, 0},
                 {0, 1, 1, 1},
                 {1, 0, 1, 0},
                 {0, 1, 0, 1}};
 
  // Function Call
  System.out.print(numberOfTriangle(arr));
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function to count the right-angled
# triangle in the given grid a[][]
def numberOfTriangle(a):
     
    N = len(a)
    M = len(a[0])
 
    # Stores the count of 1s for
    # each row[] and column[]
    rows = [0] * N
    columns = [0] * M
 
    # Find the number of 1s in
    # each of the rows[0, N - 1]
    for i in range(N):
        for j in range(M):
 
            # Increment row[i]
            if (a[i][j] == 1):
                rows[i] += 1
 
    # Find the number of 1s in
    # each of the columns[0, N - 1]
    for i in range(M):
        for j in range(N):
 
            # Increment columns[i]
            if (a[j][i] == 1):
                columns[i] += 1
 
    # Stores the count of triangles
    answer = 0
 
    for i in range(N):
        for j in range(M):
 
            # If current cell has value 1
            if (a[i][j] == 1):
 
                # Update the answer
                answer += ((rows[i] - 1) *
                      (columns[j] - 1))
 
    # Return the count
    return answer
 
# Driver Code
if __name__ == '__main__':
     
    # Given grid arr
    arr = [ [ 1, 0, 1, 0 ],
            [ 0, 1, 1, 1 ],
            [ 1, 0, 1, 0 ],
            [ 0, 1, 0, 1 ] ]
 
    # Function call
    print(numberOfTriangle(arr))
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
 
class GFG{
 
// Function to count the right-angled
// triangle in the given grid[,]a
static int numberOfTriangle(int[,] a)
{
  int N = a.GetLength(0);
  int M = a.GetLength(1);
 
  // Stores the count of 1s for
  // each []row and column[]
  int []rows = new int[N];
  int []columns = new int[M];
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for(int i = 0; i < N; ++i)
  {
    for(int j = 0; j < M; ++j)
    {
       
      // Increment row[i]
      if (a[i, j] == 1)
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for(int i = 0; i < M; ++i)
  {
    for(int j = 0; j < N; ++j)
    {
       
      // Increment columns[i]
      if (a[j, i] == 1)
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count
  // of triangles
  int answer = 0;
 
  for(int i = 0; i < N; i++)
  {
    for(int j = 0; j < M; ++j)
    {
       
      // If current cell
      // has value 1
      if (a[i, j] == 1)
      {
         
        // Update the answer
        answer += (rows[i] - 1) *
               (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given grid [,]arr
  int [,]arr = { { 1, 0, 1, 0 },
                 { 0, 1, 1, 1 },
                 { 1, 0, 1, 0 },
                 { 0, 1, 0, 1 } };
 
  // Function Call
  Console.Write(numberOfTriangle(arr));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program for the
// above approach
// Function to count the right-angled
// triangle in the given grid a
function numberOfTriangle(a)
{
  var N = a.length;
  var M = a[0].length;
 
  // Stores the count of 1s for
  // each row and column
  var rows = Array.from({length: N}, (_, i) => 0);
  var columns = Array.from({length: M}, (_, i) => 0);
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for (i = 0; i < N; ++i)
  {
    for (j = 0; j < M; ++j)
    {
      // Increment row[i]
      if (a[i][j] == 1)
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for (i = 0; i < M; ++i)
  {
    for (j = 0; j < N; ++j)
    {
      // Increment columns[i]
      if (a[j][i] == 1)
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count
  // of triangles
  var answer = 0;
 
  for (i = 0; i < N; i++)
  {
    for (j = 0; j < M; ++j)
    {
      // If current cell
      // has value 1
      if (a[i][j] == 1)
      {
        // Update the answer
        answer += (rows[i] - 1) *
                  (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
 
  // Given grid arr
  var arr = [[1, 0, 1, 0],
                 [0, 1, 1, 1],
                 [1, 0, 1, 0],
                 [0, 1, 0, 1]];
 
  // Function Call
  document.write(numberOfTriangle(arr));
 
// This code contributed by shikhasingrajput
 
</script>

16

Complejidad de tiempo: O(N*M) donde NxM son las dimensiones de la cuadrícula dada.
Complejidad espacial: O(N*M)