Compruebe si se puede formar una array palindrómica a partir de los elementos de array dados

Dada una array arr[] que consta de N ² enteros, la tarea es comprobar si se puede formar una array de dimensiones N * N a partir de los elementos de array dados, que es palíndromo . Si es posible, imprima la array palíndromo.

Una array palíndromo es aquella en la que cada una de las filas y columnas son palíndromos.

Ejemplos:

Entrada: arr[] = {5, 1, 3, 4, 5, 3, 5, 4, 5}
Salida:
Sí
5 3 5
4 1 4
5 3 5

Entrada: arr[] = {3, 4, 2, 1, 5, 6, 6, 6, 9}
Salida: No

Enfoque: A continuación se presentan algunas observaciones basadas en las cuales se puede resolver el problema dado:

Una observación importante aquí es: para poner un valor en la primera columna de la primera fila, se debe poner exactamente el mismo valor en la última columna de la misma fila para preservar el comportamiento palindrómico de la fila. Además, para hacer palíndromo de columnas, se debe poner el mismo valor en la primera columna y en la última columna de la última fila.
Por tanto, en total se necesitan 4 instancias del mismo valor para ponerlas simétricamente en la array.
Además, en el caso de una array que tiene un número impar de filas y columnas, solo se necesitan 2 instancias del mismo valor para las filas y columnas del medio porque los elementos en la fila y la columna del medio serán simétricos entre sí.
Así que aquí los elementos se pueden dividir en tres tipos:
1. Elementos que tienen una frecuencia en un múltiplo de 4.
2. Elementos que tienen una frecuencia en un múltiplo de 2.
3. El elemento que está presente sólo una vez.

Ahora, usando la técnica codiciosa , llene la array siguiendo los pasos a continuación:

Utilice una cola de prioridad para almacenar la frecuencia de los elementos de forma ordenada.
Si la fila actual no es la fila del medio, elija un elemento que tenga una frecuencia de al menos 4 para colocar estos 4 números simétricamente en las cuatro esquinas, de modo que la fila y la columna en las que se coloca permanezcan palindrómicas.
Si la fila actual es la fila del medio, elija un elemento que tenga una frecuencia de al menos 2 para colocar los valores simétricamente.
Si en algún paso no se encuentra el número requerido de elementos, entonces la array palíndromo no es posible , entonces imprima No.
De lo contrario, imprima Sí e imprima la array palindrómica formada.

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

C++14

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to fill the matrix to
// make it palindromic if possible
void fill(vector<pair<int, int> >& temp,
          priority_queue<pair<int, int> >& q,
          vector<vector<int> >& grid)
{
    // First element of priority queue
    auto it = q.top();
    q.pop();
  
    // If the frequency of element is
    // less than desired frequency
    // then not possible
    if (it.first < temp.size()) {
        cout << "No\n";
        exit(0);
    }
  
    // If possible then assign value
    // to the matrix
    for (auto c : temp) {
        grid
            = it.second;
    }
  
    // Decrease the frequency
    it.first -= temp.size();
  
    // Again push inside queue
    q.push(it);
}
  
// Function to check if palindromic
// matrix of dimension N*N can be
// formed or not
void checkPalindrome(int A[], int N)
{
    // Stores the frequency
    map<int, int> mp;
  
    // Stores in the order of frequency
    priority_queue<pair<int, int> > q;
  
    // To store the palindromic
    // matrix if exists
    vector<vector<int> >
    grid(N, vector<int>(N));
  
    for (int c = 0; c < N * N; c++) {
  
        mp[A]++;
    }
  
    // Number of rows
  
    // Assign in priority queue
    for (auto c : mp)
        q.push({ c.second, c.first });
  
    // Middle index
    int m = N / 2;
  
    // Stores the indexes to be filled
    vector<pair<int, int> > temp;
  
    for (int i = 0; i < m; i++) {
  
        for (int j = 0; j < m; j++) {
  
            // Find the opposite indexes
            // which have same value
            int revI = N - i - 1;
            int revJ = N - j - 1;
  
            temp = { { i, j },
                     { revI, j },
                     { i, revJ },
                     { revI, revJ } };
  
            // Check if all the indexes
            // in temp can be filled
            // with same value
            fill(temp, q, grid);
  
            temp.clear();
        }
    }
  
    // If N is odd then to fill the
    // middle row and middle column
    if (N & 1) {
  
        for (int i = 0; i < m; i++) {
  
            // Fill the temp
            temp = { { i, m },
                     { N - i - 1, m } };
  
            // Fill grid with temp
            fill(temp, q, grid);
  
            // Clear temp
            temp.clear();
  
            // Fill the temp
            temp = { { m, i },
                     { m, N - i - 1 } };
  
            // Fill grid with temp
            fill(temp, q, grid);
            temp.clear();
        }
  
        // For the middle element
        // of middle row and column
        temp = { { m, m } };
        fill(temp, q, grid);
    }
  
    cout << "Yes" << endl;
  
    // Print the matrix
    for (int i = 0; i < N; i++) {
  
        for (int j = 0; j < N; j++) {
  
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}
  
// Driver Code
int main()
{
    // Given array A[]
    int A[] = { 1, 1, 1, 1, 2, 3, 3, 4, 4 };
  
    int N = sizeof(A) / sizeof(A[0]);
  
    N = sqrt(N);
  
    // Function call
    checkPalindrome(A, N);
  
    return 0;
}

Producción:

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N ² )

Publicación traducida automáticamente

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

C++14

Deja una respuesta Cancelar la respuesta