Dada una array cuadrada de tamaño N x N , la tarea es comprobar si es cuadrada latina o no.
Una array cuadrada es un cuadrado latino si cada celda de la array contiene uno de N valores diferentes (en el rango [1, N]), y ningún valor se repite dentro de una fila o columna.
Ejemplos:
Input: 1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
Output: YES
Input: 2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
Output: NO
Enfoque ingenuo:
- Para cada elemento, primero verificamos si el elemento dado ya está presente en la fila y la columna dadas iterando sobre todos los elementos de la fila y la columna dadas.
- De lo contrario, verifique si el valor es menor o igual que N, si es así, pase al siguiente elemento.
- Si alguno de los puntos anteriores es falso, entonces la array no es un cuadrado latino.
Enfoque eficiente: Aquí está el enfoque más eficiente usando una estructura de datos Set en C++:
- Defina conjuntos para cada fila y cada columna y cree dos arrays de conjuntos, una para todas las filas y otra para las columnas.
- Iterar sobre todos los elementos e insertar el valor del elemento dado en el conjunto de filas correspondiente y en el conjunto de columnas correspondiente.
- Además, verifique si el valor dado es menor que N o no. Si no, escriba “NO” y regrese.
- Ahora, itere sobre todos los conjuntos de filas y conjuntos de columnas y verifique si el tamaño del conjunto es menor que N o no.
- En caso afirmativo, escriba «SÍ». De lo contrario, escriba «NO».
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to check if given matrix
// is natural latin square or not
#include <bits/stdc++.h>
using namespace std;
void CheckLatinSquare(int mat[4][4])
{
// Size of square matrix is NxN
int N = sizeof(mat[0]) / sizeof(mat[0][0]);
// Vector of N sets corresponding
// to each row.
vector<set<int> > rows(N);
// Vector of N sets corresponding
// to each column.
vector<set<int> > cols(N);
// Number of invalid elements
int invalid = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
rows[i].insert(mat[i][j]);
cols[j].insert(mat[i][j]);
if (mat[i][j] > N || mat[i][j] <= 0) {
invalid++;
}
}
}
// Number of rows with
// repetitive elements.
int numrows = 0;
// Number of columns with
// repetitive elements.
int numcols = 0;
// Checking size of every row
// and column
for (int i = 0; i < N; i++) {
if (rows[i].size() != N) {
numrows++;
}
if (cols[i].size() != N) {
numcols++;
}
}
if (numcols == 0 && numrows == 0
&& invalid == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
return;
}
// Driver code
int main()
{
int Matrix[4][4] = { { 1, 2, 3, 4 },
{ 2, 1, 4, 3 },
{ 3, 4, 1, 2 },
{ 4, 3, 2, 1 } };
// Function call
CheckLatinSquare(Matrix);
return 0;
}
Java
// Java program to check if given matrix
// is natural latin square or not
import java.util.*;
class GFG{
@SuppressWarnings("unchecked")
static void CheckLatinSquare(int mat[][])
{
// Size of square matrix is NxN
int N = mat.length;
// Vector of N sets corresponding
// to each row.
HashSet<Integer>[] rows = new HashSet[N];
// Vector of N sets corresponding
// to each column.
HashSet<Integer>[] cols = new HashSet[N];
for(int i = 0; i < N; i++)
{
rows[i] = new HashSet<Integer>();
cols[i] = new HashSet<Integer>();
}
// Number of invalid elements
int invalid = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
rows[i].add(mat[i][j]);
cols[j].add(mat[i][j]);
if (mat[i][j] > N || mat[i][j] <= 0)
{
invalid++;
}
}
}
// Number of rows with
// repetitive elements.
int numrows = 0;
// Number of columns with
// repetitive elements.
int numcols = 0;
// Checking size of every row
// and column
for(int i = 0; i < N; i++)
{
if (rows[i].size() != N)
{
numrows++;
}
if (cols[i].size() != N)
{
numcols++;
}
}
if (numcols == 0 &&
numrows == 0 && invalid == 0)
System.out.print("YES" + "\n");
else
System.out.print("NO" + "\n");
return;
}
// Driver code
public static void main(String[] args)
{
int Matrix[][] = { { 1, 2, 3, 4 },
{ 2, 1, 4, 3 },
{ 3, 4, 1, 2 },
{ 4, 3, 2, 1 } };
// Function call
CheckLatinSquare(Matrix);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check if given matrix
# is natural latin square or not
def CheckLatinSquare(mat):
# Size of square matrix is NxN
N = len(mat)
# Vector of N sets corresponding
# to each row.
rows = []
for i in range(N):
rows.append(set([]))
# Vector of N sets corresponding
# to each column.
cols = []
for i in range(N):
cols.append(set([]))
# Number of invalid elements
invalid = 0
for i in range(N):
for j in range(N):
rows[i].add(mat[i][j])
cols[j].add(mat[i][j])
if (mat[i][j] > N or mat[i][j] <= 0) :
invalid += 1
# Number of rows with
# repetitive elements.
numrows = 0
# Number of columns with
# repetitive elements.
numcols = 0
# Checking size of every row
# and column
for i in range(N):
if (len(rows[i]) != N) :
numrows+=1
if (len(cols[i]) != N) :
numcols+=1
if (numcols == 0 or numrows == 0 and invalid == 0) :
print("YES")
else:
print("NO")
return
Matrix = [ [ 1, 2, 3, 4 ],
[ 2, 1, 4, 3 ],
[ 3, 4, 1, 2 ],
[ 4, 3, 2, 1 ] ]
# Function call
CheckLatinSquare(Matrix)
# This code is contributed by decode2207.
C#
// C# program to check if given matrix
// is natural latin square or not
using System;
using System.Collections.Generic;
class GFG{
static void CheckLatinSquare(int[, ] mat)
{
// Size of square matrix is NxN
int N = mat.GetLength(0);
// List of N sets corresponding
// to each row.
HashSet<int>[] rows = new HashSet<int>[ N ];
// List of N sets corresponding
// to each column.
HashSet<int>[] cols = new HashSet<int>[ N ];
for (int i = 0; i < N; i++)
{
rows[i] = new HashSet<int>();
cols[i] = new HashSet<int>();
}
// Number of invalid elements
int invalid = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
rows[i].Add(mat[i, j]);
cols[j].Add(mat[i, j]);
if (mat[i, j] > N || mat[i, j] <= 0)
{
invalid++;
}
}
}
// Number of rows with
// repetitive elements.
int numrows = 0;
// Number of columns with
// repetitive elements.
int numcols = 0;
// Checking size of every row
// and column
for (int i = 0; i < N; i++)
{
if (rows[i].Count != N)
{
numrows++;
}
if (cols[i].Count != N)
{
numcols++;
}
}
if (numcols == 0 && numrows == 0 && invalid == 0)
Console.Write("YES" + "\n");
else
Console.Write("NO" + "\n");
return;
}
// Driver code
public static void Main(String[] args)
{
int[, ] Matrix = {{1, 2, 3, 4},
{2, 1, 4, 3},
{3, 4, 1, 2},
{4, 3, 2, 1}};
// Function call
CheckLatinSquare(Matrix);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program to check if given matrix
// is natural latin square or not
function CheckLatinSquare(mat)
{
// Size of square matrix is NxN
var N = mat.length;
// Vector of N sets corresponding
// to each row.
var rows = new Array(N);
// Vector of N sets corresponding
// to each column.
var cols = new Array(N);
for(var i = 0; i < N; i++)
{
rows[i] = new Set();
cols[i] = new Set();
}
// Number of invalid elements
var invalid = 0;
for(var i = 0; i < N; i++)
{
for(var j = 0; j < N; j++)
{
rows[i].add(mat[i][j]);
cols[j].add(mat[i][j]);
if (mat[i][j] > N || mat[i][j] <= 0)
{
invalid++;
}
}
}
// Number of rows with
// repetitive elements.
var numrows = 0;
// Number of columns with
// repetitive elements.
var numcols = 0;
// Checking size of every row
// and column
for(var i = 0; i < N; i++)
{
if (rows[i].size != N)
{
numrows++;
}
if (cols[i].size != N)
{
numcols++;
}
}
if (numcols == 0 &&
numrows == 0 && invalid == 0)
document.write("YES");
else
document.write("NO");
return;
}
// Driver code
var Matrix = [ [ 1, 2, 3, 4 ],
[ 2, 1, 4, 3 ],
[ 3, 4, 1, 2 ],
[ 4, 3, 2, 1 ] ];
// Function call
CheckLatinSquare(Matrix);
// This code is contributed by 29AjayKumar
</script>
Producción:
YES