Dados dos enteros positivos N y C . Hay una array de 2*N donde cada celda de la array se puede colorear en 0 o 1. La tarea es encontrar varias formas, la array de 2*N se forma teniendo exactamente c componentes.
Se dice que una celda está en el mismo componente que otra celda si comparte un lado con la otra celda (vecina inmediata) y es del mismo color.
Ejemplos:
Entrada: N = 2, C = 1
Salida: 2
Explicación:
C = 1 puede ser posible cuando todas las celdas de la array están coloreadas del mismo color.
Tenemos 2 opciones para colorear 0 y 1. Por lo tanto, la respuesta es 2.
Entrada: N = 1, C = 2
Salida: 2
Planteamiento: La idea para resolver este problema es usar Programación Dinámica . Construya una array 4D DP de 
tamaños, donde N es el número de columnas, C es el número de componentes y la dimensión 2*2 es la disposición en la última columna. La última columna puede tener cuatro combinaciones diferentes. Son 00, 01, 10, 11.
Cada celda de la array dp[i][j][fila1][fila2] da el número de formas de tener j componentes en i columnas cuando la disposición en la última columna es fila1, fila2 . Si el subproblema actual ha sido evaluado, es decir, dp[columna][componente][fila1][fila2] != -1, utilice este resultado; de lo contrario, calcule el valor recursivamente.
- Caso base: cuando el número de columnas es mayor que N, devuelve 0. Si el número de columnas es igual a N, la respuesta depende del número de componentes. Si los componentes son iguales a C, devuelve 1, de lo contrario, devuelve 0.
- Caso 1 : cuando la columna anterior tiene el mismo color ({0, 0} o {1, 1}) en su fila.
En este caso, los componentes aumentarán en 1 si la columna actual tiene valores diferentes en sus filas ({0, 1} o {1, 0}). Los componentes también aumentarán en 1 si la columna actual tiene el color opuesto pero con el mismo valor en sus filas. Esa es la columna actual tiene {1, 1} cuando la columna anterior tiene {0, 0}. o la columna actual tiene {0, 0} cuando la columna anterior tiene {1, 1}. Los componentes siguen siendo los mismos cuando la columna actual tiene la misma combinación que la columna anterior. - Caso 2 : cuando la columna anterior tiene el color diferente ({0, 1} o {1, 0}) en su fila.
En este caso, los componentes aumentarán en 2 si la columna actual tiene una combinación completamente opuesta a la de su columna anterior. Eso es cuando la columna actual es {1, 0} y la columna anterior es {0, 1}. o la columna actual es {0, 1} y la columna anterior es {1, 0}. En todos los demás casos, los componentes siguen siendo los mismos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// number of ways to make exactly
// C components in a 2 * N matrix
#include <bits/stdc++.h>
using namespace std;
// row1 and row2 are one
// when both are same colored
int n, k;
int dp[1024][2048][2][2];
// Function to find the number of
// ways to make exactly C components
// in a 2 * N matrix
int Ways(int col, int comp,
int row1, int row2)
{
// if No of components
// at any stage exceeds
// the given number
// then base case
if (comp > k)
return 0;
if (col > n) {
if (comp == k)
return 1;
else
return 0;
}
// Condition to check
// if already visited
if (dp[col][comp][row1][row2] != -1)
return dp[col][comp][row1][row2];
// if not visited previously
else {
int ans = 0;
// At the first column
if (col == 1) {
// color {white, white} or
// {black, black}
ans
= (ans
+ Ways(col + 1, comp + 1, 0, 0)
+ Ways(col + 1, comp + 1, 1, 1));
// Color {white, black} or
// {black, white}
ans
= (ans
+ Ways(col + 1, comp + 2, 0, 1)
+ Ways(col + 1, comp + 2, 1, 0));
}
else {
// If previous both
// rows have same color
if ((row1 && row2)
|| (!row1 && !row2)) {
// Fill with {same, same} and
// {white, black} and {black, white}
ans = (((ans
+ Ways(col + 1, comp + 1, 0, 0))
+ Ways(col + 1, comp + 1, 1, 0))
+ Ways(col + 1, comp + 1, 0, 1));
// Fill with same without
// increase in component
// as it has been
// counted previously
ans = (ans
+ Ways(col + 1, comp, 1, 1));
}
// When previous rows
// had {white, black}
if (row1 && !row2) {
ans = (((ans
+ Ways(col + 1, comp, 0, 0))
+ Ways(col + 1, comp, 1, 1))
+ Ways(col + 1, comp, 1, 0));
ans = (ans
+ Ways(col + 1, comp + 2, 0, 1));
}
// When previous rows
// had {black, white}
if (!row1 && row2) {
ans = (((ans
+ Ways(col + 1, comp, 0, 0))
+ Ways(col + 1, comp, 1, 1))
+ Ways(col + 1, comp, 0, 1));
ans = (ans
+ Ways(col + 1, comp + 2, 1, 0));
}
}
// Memoization
return dp[col][comp][row1][row2] = ans;
}
}
// Driver Code
signed main()
{
n = 2;
k = 1;
memset(dp, -1, sizeof(dp));
// Initially at first column
// with 0 components
cout << Ways(1, 0, 0, 0);
return 0;
}
Java
// Java implementation to find the
// number of ways to make exactly
// C components in a 2 * N matrix
class GFG{
// row1 and row2 are one
// when both are same colored
static int n, k;
static int [][][][]dp = new int[1024][2048][2][2];
// Function to find the number of
// ways to make exactly C components
// in a 2 * N matrix
static int Ways(int col, int comp,
int row1, int row2)
{
// if No of components
// at any stage exceeds
// the given number
// then base case
if (comp > k)
return 0;
if (col > n)
{
if (comp == k)
return 1;
else
return 0;
}
// Condition to check
// if already visited
if (dp[col][comp][row1][row2] != -1)
return dp[col][comp][row1][row2];
// if not visited previously
else
{
int ans = 0;
// At the first column
if (col == 1)
{
// color {white, white} or
// {black, black}
ans = (ans + Ways(col + 1, comp + 1, 0, 0) +
Ways(col + 1, comp + 1, 1, 1));
// Color {white, black} or
// {black, white}
ans = (ans + Ways(col + 1, comp + 2, 0, 1) +
Ways(col + 1, comp + 2, 1, 0));
}
else
{
// If previous both
// rows have same color
if ((row1 > 0 && row2 > 0) ||
(row1 == 0 && row2 ==0))
{
// Fill with {same, same} and
// {white, black} and {black, white}
ans = (((ans +
Ways(col + 1, comp + 1, 0, 0)) +
Ways(col + 1, comp + 1, 1, 0)) +
Ways(col + 1, comp + 1, 0, 1));
// Fill with same without
// increase in component
// as it has been
// counted previously
ans = (ans +
Ways(col + 1, comp, 1, 1));
}
// When previous rows
// had {white, black}
if (row1 > 0 && row2 == 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 1, 0));
ans = (ans +
Ways(col + 1, comp + 2, 0, 1));
}
// When previous rows
// had {black, white}
if (row1 ==0 && row2 > 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 0, 1));
ans = (ans +
Ways(col + 1, comp + 2, 1, 0));
}
}
// Memoization
return dp[col][comp][row1][row2] = ans;
}
}
// Driver Code
public static void main(String[] args)
{
n = 2;
k = 1;
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 2048; j++)
for (int k = 0; k < 2; k++)
for (int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;
// Initially at first column
// with 0 components
System.out.print(Ways(1, 0, 0, 0));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation to find the # number of ways to make exactly # C components in a 2 * N matrix # row1 and row2 are one # when both are same colored n = 0 k = 0 dp = [[[[-1 for i in range(2)] for j in range(2)]for k in range(2048)]for l in range(1024)] # Function to find the number of # ways to make exactly C components # in a 2 * N matrix def Ways(col, comp, row1, row2): global n, k, dp # if No of components # at any stage exceeds # the given number # then base case if (comp > k): return 0 if (col > n): if (comp == k): return 1 else: return 0 # Condition to check # if already visited if (dp[col][comp][row1][row2] != -1): return dp[col][comp][row1][row2] # if not visited previously else: ans = 0 # At the first column if (col == 1): # color white, white or # black, black ans = (ans + Ways(col + 1, comp + 1, 0, 0) + Ways(col + 1, comp + 1, 1, 1)) # Color white, black or # black, white ans = (ans + Ways(col + 1, comp + 2, 0, 1) + Ways(col + 1, comp + 2, 1, 0)) else: # If previous both # rows have same color if ((row1 and row2) or (not row1 and not row2)): # Fill with same, same and # white, black and black, white ans = (((ans + Ways(col + 1, comp + 1, 0, 0)) + Ways(col + 1, comp + 1, 1, 0)) + Ways(col + 1, comp + 1, 0, 1)) # Fill with same without # increase in component # as it has been # counted previously ans = (ans + Ways(col + 1, comp, 1, 1)) # When previous rows # had white, black if (row1 and not row2): ans = (((ans + Ways(col + 1, comp, 0, 0)) + Ways(col + 1, comp, 1, 1)) + Ways(col + 1, comp, 1, 0)) ans = (ans + Ways(col + 1, comp + 2, 0, 1)) # When previous rows # had black, white if (not row1 and row2): ans = (((ans + Ways(col + 1, comp, 0, 0)) + Ways(col + 1, comp, 1, 1)) + Ways(col + 1, comp, 0, 1)) ans = (ans + Ways(col + 1, comp + 2, 1, 0)) # Memoization dp[col][comp][row1][row2] = ans return dp[col][comp][row1][row2] # Driver Code n = 2 k = 1 # Initially at first column # with 0 components print(Ways(1, 0, 0, 0)) # This code is contributed by Shubham Singh
C#
// C# implementation to find the
// number of ways to make exactly
// C components in a 2 * N matrix
using System;
class GFG{
// row1 and row2 are one
// when both are same colored
static int n, k;
static int [,,,]dp = new int[ 1024, 2048, 2, 2 ];
// Function to find the number of
// ways to make exactly C components
// in a 2 * N matrix
static int Ways(int col, int comp,
int row1, int row2)
{
// If No of components
// at any stage exceeds
// the given number
// then base case
if (comp > k)
return 0;
if (col > n)
{
if (comp == k)
return 1;
else
return 0;
}
// Condition to check
// if already visited
if (dp[ col, comp, row1, row2 ] != -1)
return dp[ col, comp, row1, row2 ];
// If not visited previously
else
{
int ans = 0;
// At the first column
if (col == 1)
{
// color {white, white} or
// {black, black}
ans = (ans + Ways(col + 1, comp + 1, 0, 0) +
Ways(col + 1, comp + 1, 1, 1));
// Color {white, black} or
// {black, white}
ans = (ans + Ways(col + 1, comp + 2, 0, 1) +
Ways(col + 1, comp + 2, 1, 0));
}
else
{
// If previous both
// rows have same color
if ((row1 > 0 && row2 > 0) ||
(row1 == 0 && row2 == 0))
{
// Fill with {same, same} and
// {white, black} and {black, white}
ans = (((ans +
Ways(col + 1, comp + 1, 0, 0)) +
Ways(col + 1, comp + 1, 1, 0)) +
Ways(col + 1, comp + 1, 0, 1));
// Fill with same without
// increase in component
// as it has been
// counted previously
ans = (ans +
Ways(col + 1, comp, 1, 1));
}
// When previous rows
// had {white, black}
if (row1 > 0 && row2 == 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 1, 0));
ans = (ans +
Ways(col + 1, comp + 2, 0, 1));
}
// When previous rows
// had {black, white}
if (row1 == 0 && row2 > 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 0, 1));
ans = (ans +
Ways(col + 1, comp + 2, 1, 0));
}
}
// Memoization
return dp[ col, comp, row1, row2 ] = ans;
}
}
// Driver Code
public static void Main(String[] args)
{
n = 2;
k = 1;
for(int i = 0; i < 1024; i++)
for(int j = 0; j < 2048; j++)
for(int K = 0; K < 2; K++)
for(int l = 0; l < 2; l++)
dp[ i, j, K, l ] = -1;
// Initially at first column
// with 0 components
Console.Write(Ways(1, 0, 0, 0));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the
// number of ways to make exactly
// C components in a 2 * N matrix
// row1 and row2 are one
// when both are same colored
var n, k;
var dp = new Array(1024).fill(0).map(() => new Array(2048).fill(0).map(() => new Array(2).fill(0).map(() => new Array(2).fill(0))));
// Function to find the number of
// ways to make exactly C components
// in a 2 * N matrix
function Ways(col, comp, row1, row2)
{
// if No of components
// at any stage exceeds
// the given number
// then base case
if (comp > k)
return 0;
if (col > n)
{
if (comp == k)
return 1;
else
return 0;
}
// Condition to check
// if already visited
if (dp[col][comp][row1][row2] != -1)
return dp[col][comp][row1][row2];
// if not visited previously
else
{
var ans = 0;
// At the first column
if (col == 1)
{
// color {white, white} or
// {black, black}
ans = (ans + Ways(col + 1, comp + 1, 0, 0) +
Ways(col + 1, comp + 1, 1, 1));
// Color {white, black} or
// {black, white}
ans = (ans + Ways(col + 1, comp + 2, 0, 1) +
Ways(col + 1, comp + 2, 1, 0));
}
else
{
// If previous both
// rows have same color
if ((row1 > 0 && row2 > 0) ||
(row1 == 0 && row2 ==0))
{
// Fill with {same, same} and
// {white, black} and {black, white}
ans = (((ans +
Ways(col + 1, comp + 1, 0, 0)) +
Ways(col + 1, comp + 1, 1, 0)) +
Ways(col + 1, comp + 1, 0, 1));
// Fill with same without
// increase in component
// as it has been
// counted previously
ans = (ans +
Ways(col + 1, comp, 1, 1));
}
// When previous rows
// had {white, black}
if (row1 > 0 && row2 == 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 1, 0));
ans = (ans +
Ways(col + 1, comp + 2, 0, 1));
}
// When previous rows
// had {black, white}
if (row1 ==0 && row2 > 0)
{
ans = (((ans +
Ways(col + 1, comp, 0, 0)) +
Ways(col + 1, comp, 1, 1)) +
Ways(col + 1, comp, 0, 1));
ans = (ans +
Ways(col + 1, comp + 2, 1, 0));
}
}
// Memoization
return dp[col][comp][row1][row2] = ans;
}
}
// Driver Code
n = 2;
k = 1;
for(var i = 0; i < 1024; i++){
for(var j = 0; j < 2048; j++){
for(var K = 0; K < 2; K++){
for(var l = 0; l < 2; l++){
dp[i][j][K][l] = -1;
}
}
}
}
// Initially at first column
// with 0 components
document.write(Ways(1, 0, 0, 0));
// This code is contributed by Shubham Singh
</script>
Producción:
2
Complejidad de tiempo: O(N*C)
Publicación traducida automáticamente
Artículo escrito por ujjwalmittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA