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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA