Colorea una cuadrícula de modo que todas las celdas del mismo color estén conectadas horizontal o verticalmente

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 . 

  1. Cree una nueva array 2D que será nuestra cuadrícula final. Llamémoslo dp[][].
  2. Atraviesa la array de colores A[]
  3. 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
  4. 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

Deja una respuesta

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