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)