Divida Matrix en K grupos de celdas adyacentes que tengan una diferencia mínima entre los grupos de tamaño máximo y mínimo

Dadas N filas y M columnas de una array, la tarea es llenar las celdas de la array usando los primeros K enteros tales que:

  • Cada grupo de celdas se denota con un solo número entero.
  • La diferencia entre el grupo que contiene el número máximo y mínimo de celdas debe ser mínima.
  • Todas las celdas del mismo grupo deben ser contiguas, es decir, para cualquier grupo, dos celdas adyacentes deben seguir la regla |x i+1 – x i | + |y i+1 – y i | = 1 .

Ejemplos:

Entrada: N = 5, M = 5, K = 6
Salida:
1 1 1 1 1
3 2 2 2 2
3 3 3 4 4
5 5 5 4 4
5 6 6 6 6
Explicación:
La array anterior sigue todas las condiciones anteriores y dividiendo la array en K grupos diferentes.

Entrada: N = 2, M = 3, K = 3
Salida:
1 1 2
3 3 2
Explicación:
Para hacer tres grupos de la array, cada uno debe tener el grupo de tamaño dos.
Entonces, para reducir la diferencia entre el grupo que contiene el número máximo y mínimo de celdas y todas las celdas de la array se utilizan para hacer los K grupos diferentes que tienen todos los elementos adyacentes del mismo grupo siguiendo el |x i + 1 – x i | + |y yo + 1 – y yo | = 1 también.

Enfoque: A continuación se detallan los pasos:

  • Cree la array de tamaño N * M .
  • Para reducir la diferencia entre el grupo que contiene el número máximo y mínimo de celdas, llene toda la parte con al menos (N*M)/K celdas.
  • La parte restante contendrá (N * M)/ K + 1 no de celdas.
  • Para seguir las reglas dadas, atraviese la array y llénela con las diferentes partes correspondientes.
  • Imprima la array después de los pasos anteriores.

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 fill the matrix with
// the given conditions
void fillMatrix(int** mat, int& row,
                int& col, int sizeOfpart,
                int noOfPart, int& start,
                int m, int& flag)
{
 
    // Count of parts with size sizeOfPart
    for (int i = 0; i < noOfPart; ++i) {
 
        int count = 0;
 
        while (count < sizeOfpart) {
 
            // Assigning the cell
            // with no of groups
            mat[row][col] = start;
 
            // Update row
            if (col == m - 1
                && flag == 1) {
                row++;
                col = m;
                flag = 0;
            }
            else if (col == 0
                     && flag == 0) {
                row++;
                col = -1;
                flag = 1;
            }
 
            // Update col
            if (flag == 1) {
                col++;
            }
            else {
                col--;
            }
 
            // Increment count
            count++;
        }
 
        // For new group increment start
        start++;
    }
}
 
// Function to return the reference of
// the matrix to be filled
int** findMatrix(int N, int M, int k)
{
 
    // Create matrix of size N*M
    int** mat = (int**)malloc(
        N * sizeof(int*));
 
    for (int i = 0; i < N; ++i) {
        mat[i] = (int*)malloc(
            M * sizeof(int));
    }
 
    // Starting index of the matrix
    int row = 0, col = 0;
 
    // Size of one group
    int size = (N * M) / k;
    int rem = (N * M) % k;
 
    // Element to assigned to matrix
    int start = 1, flag = 1;
 
    // Fill the matrix that have rem
    // no of parts with size size + 1
    fillMatrix(mat, row, col, size + 1,
               rem, start, M, flag);
 
    // Fill the remaining number of parts
    // with each part size is 'size'
    fillMatrix(mat, row, col, size,
               k - rem, start, M, flag);
 
    // Return the matrix
    return mat;
}
 
// Function to print the matrix
void printMatrix(int** mat, int N,
                 int M)
{
    // Traverse the rows
    for (int i = 0; i < N; ++i) {
 
        // Traverse the columns
        for (int j = 0; j < M; ++j) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given N, M, K
    int N = 5, M = 5, K = 6;
 
    // Function Call
    int** mat = findMatrix(N, M, K);
 
    // Function Call to print matrix
    printMatrix(mat, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int N, M;
static int [][]mat;
static int row, col, start, flag;
 
// Function to fill the matrix with
// the given conditions
static void fillMatrix(int sizeOfpart,
                       int noOfPart,
                       int m)
{
     
    // Count of parts with size sizeOfPart
    for(int i = 0; i < noOfPart; ++i)
    {
        int count = 0;
 
        while (count < sizeOfpart)
        {
             
            // Assigning the cell
            // with no of groups
            mat[row][col] = start;
 
            // Update row
            if (col == m - 1 && flag == 1)
            {
                row++;
                col = m;
                flag = 0;
            }
            else if (col == 0 && flag == 0)
            {
                row++;
                col = -1;
                flag = 1;
            }
 
            // Update col
            if (flag == 1)
            {
                col++;
            }
            else
            {
                col--;
            }
 
            // Increment count
            count++;
        }
 
        // For new group increment start
        start++;
    }
}
 
// Function to return the reference of
// the matrix to be filled
static void findMatrix(int k)
{
     
    // Create matrix of size N*M
    mat = new int[M][N];
 
    // Starting index of the matrix
    row = 0;
    col = 0;
 
    // Size of one group
    int size = (N * M) / k;
    int rem = (N * M) % k;
 
    // Element to assigned to matrix
    start = 1;
    flag = 1;
 
    // Fill the matrix that have rem
    // no of parts with size size + 1
    fillMatrix(size + 1, rem, M);
 
    // Fill the remaining number of parts
    // with each part size is 'size'
    fillMatrix(size, k - rem, M);
}
 
// Function to print the matrix
static void printMatrix()
{
     
    // Traverse the rows
    for(int i = 0; i < N; ++i)
    {
         
        // Traverse the columns
        for(int j = 0; j < M; ++j)
        {
            System.out.print(mat[i][j] + " ");
        }
        System.out.println();
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N, M, K
    N = 5;
    M = 5;
    int K = 6;
 
    // Function Call
    findMatrix(K);
 
    // Function Call to print matrix
    printMatrix();
}
}
 
// This code is contributed by Amit Katiyar

C#

// C# program for the
// above approach
using System;
class GFG{
     
static int N, M;
static int [,]mat;
static int row, col,
           start, flag;
 
// Function to fill the
// matrix with the given
// conditions
static void fillMatrix(int sizeOfpart,
                       int noOfPart,
                       int m)
{   
  // Count of parts with size
  // sizeOfPart
  for(int i = 0;
          i < noOfPart; ++i)
  {
    int count = 0;
 
    while (count < sizeOfpart)
    {
      // Assigning the cell
      // with no of groups
      mat[row, col] = start;
 
      // Update row
      if (col == m - 1 &&
          flag == 1)
      {
        row++;
        col = m;
        flag = 0;
      }
      else if (col == 0 &&
               flag == 0)
      {
        row++;
        col = -1;
        flag = 1;
      }
 
      // Update col
      if (flag == 1)
      {
        col++;
      }
      else
      {
        col--;
      }
 
      // Increment count
      count++;
    }
 
    // For new group increment
    // start
    start++;
  }
}
 
// Function to return the
// reference of the matrix
// to be filled
static void findMatrix(int k)
{   
  // Create matrix of
  // size N*M
  mat = new int[M, N];
 
  // Starting index of the
  // matrix
  row = 0;
  col = 0;
 
  // Size of one group
  int size = (N * M) / k;
  int rem = (N * M) % k;
 
  // Element to assigned to
  // matrix
  start = 1;
  flag = 1;
 
  // Fill the matrix that have
  // rem no of parts with size
  // size + 1
  fillMatrix(size + 1,
             rem, M);
 
  // Fill the remaining number
  // of parts with each part
  // size is 'size'
  fillMatrix(size, k - rem, M);
}
 
// Function to print the
// matrix
static void printMatrix()
{   
  // Traverse the rows
  for(int i = 0; i < N; ++i)
  {
    // Traverse the columns
    for(int j = 0; j < M; ++j)
    {
      Console.Write(mat[i, j] +
                    " ");
    }
    Console.WriteLine();
  }
}
 
// Driver Code
public static void Main(String[] args)
{   
  // Given N, M, K
  N = 5;
  M = 5;
  int K = 6;
 
  // Function Call
  findMatrix(K);
 
  // Function Call to
  // print matrix
  printMatrix();
}
}
 
// This code is contributed by 29AjayKumar
Producción: 

1 1 1 1 1 
3 2 2 2 2 
3 3 3 4 4 
5 5 5 4 4 
5 6 6 6 6






 

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)

Publicación traducida automáticamente

Artículo escrito por dreamer07 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 *