Dados tres enteros R, C, N y una array arr[] de tamaño N . La tarea es colorear todas las celdas de una cuadrícula de filas R y columnas C de modo que todas las celdas del mismo color estén conectadas horizontal o verticalmente. N representa los colores numerados del 1 al N y arr[] denota la cantidad de cada color. La cantidad total de color es exactamente igual al número total de celdas de la cuadrícula.
Acercarse:
Entrada: R = 3, C = 5, N = 5, arr[] = {1, 2, 3, 4, 5}
Salida:
1 4 4 4 3
2 5 4 5 3
2 5 5 5 3
Explicación: Colores disponibles son 1 (cuenta = 1), 2 (cuenta = 2), 3 (cuenta = 3), etc.
Para el color 5: podemos llegar a todos los 5 de color yendo horizontal o verticalmente a través del mismo color 5.
De manera similar para el color 3, el la fila más a la derecha contiene los 3, etc.
De manera similar, para el resto de los colores 1, 2, 4.
A continuación se muestra una cuadrícula no válida:
1 4 3 4 4
2 5 4 5 3
2 5 5 5 3
Esto se debe a que la conexión de los colores 3 y 4 se ha roto por la posición inválida de 3
en la posición (0, 2). Ya no podemos atravesar todos los 4 o todos los 3, horizontal o verticalmente, pasando solo por los respectivos 3 y 4.
Entrada : R = 2, C = 2, N = 3, arr[] = {2, 1, 1}
Salida:
1 1
2 3
Acercarse:
A primera vista, podría parecer que se requieren algoritmos gráficos. Sin embargo, vamos a seguir un algoritmo voraz optimizado .
- Cree una nueva array 2D que será nuestra cuadrícula final. Llamémoslo dp[][].
- Atraviesa la array de colores A[]
- Para cada color, tengo cantidades A[i]
- Si la fila es una fila impar, complete la array dp de izquierda a derecha
- De lo contrario, si es una fila par, llénala de derecha a izquierda
- Si la cantidad de color se agota, pasa al siguiente color con avidez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to Color a grid
// such that all same color cells
// are connected either
// horizontally or vertically
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int>& arr,
int r, int c)
{
// Current color
int idx = 1;
// final grid
int dp[r];
for (int i = 0; i < r; i++) {
// if even row
if (i % 2 == 0) {
// traverse from left to
// right
for (int j = 0; j < c; j++) {
// if color has been exhausted
//, move to the next color
if (arr[idx - 1] == 0)
idx++;
// color the grid at
// this position
dp[i][j] = idx;
// reduce the color count
arr[idx - 1]--;
}
}
else {
// traverse from right to
// left for odd rows
for (int j = c - 1; j >= 0; j--) {
if (arr[idx - 1] == 0)
idx++;
dp[i][j] = idx;
arr[idx - 1]--;
}
}
}
// print the grid
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
cout << dp[i][j] << " ";
}
cout << endl;
}
}
// Driver code
int main()
{
int r = 3, c = 5;
int n = 5;
vector<int> arr
= { 1, 2, 3, 4, 5 };
solve(arr, r, c);
return 0;
}
Java
// Java program to color a grid
// such that all same color cells
// are connected either
// horizontally or vertically
import java.util.*;
class GFG{
static void solve(List<Integer> arr,
int r, int c)
{
// Current color
int idx = 1;
// Final grid
int[][] dp = new int[r];
for(int i = 0; i < r; i++)
{
// If even row
if (i % 2 == 0)
{
// Traverse from left to
// right
for(int j = 0; j < c; j++)
{
// If color has been exhausted
//, move to the next color
if (arr.get(idx - 1) == 0)
idx++;
// Color the grid at
// this position
dp[i][j] = idx;
// Reduce the color count
arr.set(idx - 1,
arr.get(idx - 1) - 1);
}
}
else
{
// Traverse from right to
// left for odd rows
for(int j = c - 1; j >= 0; j--)
{
if (arr.get(idx - 1) == 0)
idx++;
dp[i][j] = idx;
arr.set(idx - 1,
arr.get(idx - 1) - 1);
}
}
}
// Print the grid
for(int i = 0; i < r; ++i)
{
for(int j = 0; j < c; ++j)
{
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args)
{
int r = 3, c = 5;
int n = 5;
List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5);
solve(arr, r, c);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to color a grid # such that all same color cells # are connected either # horizontally or vertically def solve(arr, r, c): # Current color idx = 1 # Final grid dp = [[0 for i in range(c)] for i in range(r)] for i in range(r): # If even row if (i % 2 == 0): # Traverse from left to # right for j in range(c): # If color has been exhausted, # move to the next color if (arr[idx - 1] == 0): idx += 1 # Color the grid at # this position # print(i,j) dp[i][j] = idx # Reduce the color count arr[idx - 1] -= 1 else: # Traverse from right to # left for odd rows for j in range(c - 1, -1, -1): if (arr[idx - 1] == 0): idx += 1 dp[i][j] = idx arr[idx - 1] -= 1 # Print the grid for i in range(r): for j in range(c): print(dp[i][j], end = " ") print() # Driver code if __name__ == '__main__': r = 3 c = 5 n = 5 arr = [ 1, 2, 3, 4, 5 ] solve(arr, r, c) # This code is contributed by mohit kumar 29
C#
// C# program to color a grid
// such that all same color cells
// are connected either
// horizontally or vertically
using System;
using System.Collections.Generic;
class GFG{
static void solve(List<int> arr,
int r, int c)
{
// Current color
int idx = 1;
// Final grid
int[,] dp = new int[r, c];
for(int i = 0; i < r; i++)
{
// If even row
if (i % 2 == 0)
{
// Traverse from left to
// right
for(int j = 0; j < c; j++)
{
// If color has been exhausted,
// move to the next color
if (arr[idx - 1] == 0)
idx++;
// Color the grid at
// this position
dp[i, j] = idx;
// Reduce the color count
arr[idx - 1] = arr[idx - 1] - 1;
}
}
else
{
// Traverse from right to
// left for odd rows
for(int j = c - 1; j >= 0; j--)
{
if (arr[idx - 1] == 0)
idx++;
dp[i, j] = idx;
arr[idx - 1] = arr[idx - 1] - 1;
}
}
}
// Print the grid
for(int i = 0; i < r; ++i)
{
for(int j = 0; j < c; ++j)
{
Console.Write(dp[i, j] + " ");
}
Console.Write('\n');
}
}
// Driver Code
public static void Main (string[] args)
{
int r = 3, c = 5;
//int n = 5;
List<int> arr = new List<int>();
arr.Add(1);
arr.Add(2);
arr.Add(3);
arr.Add(4);
arr.Add(5);
solve(arr, r, c);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript Program to Color a grid
// such that all same color cells
// are connected either
// horizontally or vertically
function solve(arr,r,c)
{
// Current color
var idx = 1;
// final grid
var dp = new Array(r);
var i,j;
for(i=0;i<r;i++)
dp[i] = new Array(c);
for(i = 0; i < r; i++) {
// if even row
if (i % 2 == 0) {
// traverse from left to
// right
for(j = 0; j < c; j++) {
// if color has been exhausted
//, move to the next color
if (arr[idx - 1] == 0)
idx++;
// color the grid at
// this position
dp[i][j] = idx;
// reduce the color count
arr[idx - 1]--;
}
}
else {
// traverse from right to
// left for odd rows
for (j = c - 1; j >= 0; j--) {
if (arr[idx - 1] == 0)
idx++;
dp[i][j] = idx;
arr[idx - 1]--;
}
}
}
// print the grid
for(i = 0; i < r; ++i) {
for(j = 0; j < c; ++j) {
document.write(dp[i][j] + " ");
}
document.write("<br>");
}
}
// Driver code
var r = 3, c = 5;
var n = 5;
var arr = [1, 2, 3, 4, 5];
solve(arr, r, c);
</script>
Producción:
1 2 2 3 3 4 4 4 4 3 5 5 5 5 5
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA