Comprobar si una array es un cuadrado latino o no

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: 

  1. 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.
  2. De lo contrario, verifique si el valor es menor o igual que N, si es así, pase al siguiente elemento.
  3. 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++:

  1. Defina conjuntos para cada fila y cada columna y cree dos arrays de conjuntos, una para todas las filas y otra para las columnas.
  2. 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.
  3. Además, verifique si el valor dado es menor que N o no. Si no, escriba “NO” y regrese.
  4. 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.
  5. 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

 

Publicación traducida automáticamente

Artículo escrito por manoj_26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *