Dados tres números enteros N , P y K , la tarea es encontrar el número de formas de pintar celdas K de una cuadrícula de 3 x N de modo que no se pinten celdas adyacentes y tampoco queden columnas P continuas sin pintar.
Nota : las celdas diagonales no se consideran celdas adyacentes.
Ejemplos:
Entrada: N = 1, P = 3, K = 1
Salida: 3
Hay 3 formas de pintar 1 celda en una cuadrícula de 3 x 1.
Entrada: N = 2, P = 2, K = 2
Salida: 8
Hay 8 formas de pintar 2 celdas en una cuadrícula de 3×2.
Las combinaciones de celdas que están pintadas se muestran a continuación:
1) (0, 0) y (1, 1)
2) (0, 0) y (2, 1)
3) (0, 0) y (2, 0)
4 ) (1, 0) y (0, 1)
5) (1, 0) y (2, 1)
6) (2, 0) y (0, 1)
7) (2, 0) y (1, 1) )
8) (0, 1) y (2, 1)
Enfoque: La idea es utilizar Programación Dinámica para resolver este problema. Como sabemos por el problema que
la columna se puede pintar sólo cuando
la columna no está pintada. Si
columna no está pintada, entonces tenemos los siguientes cinco casos:
- Pinta la primera Fila.
- Pinta la segunda fila.
- Pinta la tercera fila.
- Pinte la primera y la tercera fila.
- Deje la columna actual si al menos una
- La columna está pintada.
Por lo tanto, usando este hecho podemos resolver este problema fácilmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// number of ways to paint K cells of
// 3 x N grid such that No two adjacent
// cells are painted
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
#define MAX 301
#define MAXP 3
#define MAXK 600
#define MAXPREV 4
int dp[MAX][MAXP + 1][MAXK][MAXPREV + 1];
// Visited array to keep track
// of which columns were painted
bool vis[MAX];
// Recursive Function to compute the
// number of ways to paint the K cells
// of the 3 x N grid
int helper(int col, int prevCol,
int painted, int prev,
int N, int P, int K)
{
// Condition to check if total
// cells painted are K
if (painted >= K) {
int continuousCol = 0;
int maxContinuousCol = 0;
// Check if any P continuous
// columns were left unpainted
for (int i = 0; i < N; i++) {
if (vis[i] == false)
continuousCol++;
else {
maxContinuousCol
= max(maxContinuousCol,
continuousCol);
continuousCol = 0;
}
}
maxContinuousCol = max(
maxContinuousCol,
continuousCol);
// Condition to check if no P
// continuous columns were
// left unpainted
if (maxContinuousCol < P)
return 1;
// return 0 if there are P
// continuous columns are
// left unpainted
return 0;
}
// Condition to check if No
// further cells can be
// painted, so return 0
if (col >= N)
return 0;
// if already calculated the value
// return the val instead
// of calculating again
if (dp[col][prevCol][painted][prev] != -1)
return dp[col][prevCol][painted][prev];
int res = 0;
// Previous column was not painted
if (prev == 0) {
// Column is painted so,
// make vis[col]=true
vis[col] = true;
res += (helper(
col + 1, 0, painted + 1,
1, N, P, K))
% mod;
res += (helper(
col + 1, 0, painted + 1,
2, N, P, K))
% mod;
res += (helper(
col + 1, 0, painted + 1,
3, N, P, K))
% mod;
// Condition to check if the number
// of cells to be painted is equal
// to or more than 2, then we can
// paint first and third row
if (painted + 2 <= K) {
res
+= (helper(
col + 1, 0, painted + 2,
4, N, P, K))
% mod;
}
vis[col] = false;
// Condition to check if number of
// previous continuous columns left
// unpainted is less than P
if (prevCol + 1 < P) {
res
+= (helper(
col + 1, prevCol + 1,
painted, 0, N, P, K))
% mod;
}
}
// Condition to check if first row
// was painted in previous column
else if (prev == 1) {
vis[col] = true;
res += (helper(
col + 1, 0, painted + 1,
2, N, P, K))
% mod;
res += (helper(
col + 1, 0, painted + 1,
3, N, P, K))
% mod;
vis[col] = false;
if (prevCol + 1 < P) {
res += (helper(
col + 1, prevCol + 1,
painted, 0, N, P, K))
% mod;
}
}
// Condition to check if second row
// was painted in previous column
else if (prev == 2) {
vis[col] = true;
res += (helper(
col + 1, 0, painted + 1,
1, N, P, K))
% mod;
res += (helper(
col + 1, 0, painted + 1,
3, N, P, K))
% mod;
// Condition to check if the number
// of cells to be painted is equal to
// or more than 2, then we can
// paint first and third row
if (painted + 2 <= K) {
res
+= (helper(
col + 1, 0, painted + 2,
4, N, P, K))
% mod;
}
vis[col] = false;
if (prevCol + 1 < P) {
res
+= (helper(
col + 1, prevCol + 1,
painted, 0, N, P, K))
% mod;
}
}
// Condition to check if third row
// was painted in previous column
else if (prev == 3) {
vis[col] = true;
res += (helper(
col + 1, 0, painted + 1,
1, N, P, K))
% mod;
res += (helper(
col + 1, 0, painted + 1,
2, N, P, K))
% mod;
vis[col] = false;
if (prevCol + 1 < P) {
res += (helper(
col + 1, prevCol + 1,
painted, 0, N, P, K))
% mod;
}
}
// Condition to check if first and
// third row were painted
// in previous column
else {
vis[col] = true;
res += (helper(
col + 1, 0, painted + 1,
2, N, P, K))
% mod;
vis[col] = false;
if (prevCol + 1 < P) {
res += (helper(
col + 1, prevCol + 1,
painted, 0, N, P, K))
% mod;
}
}
// Memoize the data and return the
// Computed value
return dp[col][prevCol][painted][prev]
= res % mod;
}
// Function to find the number of
// ways to paint 3 x N grid
int solve(int n, int p, int k)
{
// Set all values
// of dp to -1;
memset(dp, -1, sizeof(dp));
// Set all values of Visited
// array to false
memset(vis, false, sizeof(vis));
return helper(0, 0, 0, 0, n, p, k);
}
// Driver Code
int main()
{
int N = 2, K = 2, P = 2;
cout << solve(N, P, K) << endl;
return 0;
}
Java
// Java implementation to find the
// number of ways to paint K cells of
// 3 x N grid such that No two adjacent
// cells are painted
import java.util.*;
class GFG{
static int mod = (int)(1e9 + 7);
static final int MAX = 301;
static final int MAXP = 3;
static final int MAXK = 600;
static final int MAXPREV = 4;
static int [][][][]dp = new int[MAX][MAXP + 1][MAXK][MAXPREV + 1];
// Visited array to keep track
// of which columns were painted
static boolean []vis = new boolean[MAX];
// Recursive Function to compute the
// number of ways to paint the K cells
// of the 3 x N grid
static int helper(int col, int prevCol,
int painted, int prev,
int N, int P, int K)
{
// Condition to check if total
// cells painted are K
if (painted >= K)
{
int continuousCol = 0;
int maxContinuousCol = 0;
// Check if any P continuous
// columns were left unpainted
for(int i = 0; i < N; i++)
{
if (vis[i] == false)
continuousCol++;
else
{
maxContinuousCol = Math.max(
maxContinuousCol,
continuousCol);
continuousCol = 0;
}
}
maxContinuousCol = Math.max(
maxContinuousCol,
continuousCol);
// Condition to check if no P
// continuous columns were
// left unpainted
if (maxContinuousCol < P)
return 1;
// return 0 if there are P
// continuous columns are
// left unpainted
return 0;
}
// Condition to check if No
// further cells can be
// painted, so return 0
if (col >= N)
return 0;
// If already calculated the value
// return the val instead
// of calculating again
if (dp[col][prevCol][painted][prev] != -1)
return dp[col][prevCol][painted][prev];
int res = 0;
// Previous column was not painted
if (prev == 0)
{
// Column is painted so,
// make vis[col]=true
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal
// to or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
// Condition to check if number of
// previous continuous columns left
// unpainted is less than P
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first row
// was painted in previous column
else if (prev == 1)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if second row
// was painted in previous column
else if (prev == 2)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal to
// or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if third row
// was painted in previous column
else if (prev == 3)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first and
// third row were painted
// in previous column
else
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Memoize the data and return
// the computed value
return dp[col][prevCol][painted][prev] = res % mod;
}
// Function to find the number of
// ways to paint 3 x N grid
static int solve(int n, int p, int K)
{
// Set all values
// of dp to -1;
for(int i = 0; i < MAX; i++)
for(int j = 0; j < MAXP + 1; j++)
for(int k = 0; k < MAXK; k++)
for(int l = 0; l < MAXPREV + 1; l++)
dp[i][j][k][l] = -1;
// Set all values of Visited
// array to false
Arrays.fill(vis, false);
return helper(0, 0, 0, 0, n, p, K);
}
// Driver Code
public static void main(String[] args)
{
int N = 2, K = 2, P = 2;
System.out.print(solve(N, P, K) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 implementation to find the # number of ways to paint K cells of # 3 x N grid such that No two adjacent # cells are painted mod = 1e9 + 7 MAX = 301 MAXP = 3 MAXK = 600 MAXPREV = 4 dp = [[[[-1 for x in range(MAXPREV + 1)]for y in range(MAXK)] for z in range(MAXP + 1)]for k in range(MAX)] # Visited array to keep track # of which columns were painted vis = [False] * MAX # Recursive Function to compute the # number of ways to paint the K cells # of the 3 x N grid def helper(col, prevCol, painted, prev, N, P, K): # Condition to check if total # cells painted are K if (painted >= K): continuousCol = 0 maxContinuousCol = 0 # Check if any P continuous # columns were left unpainted for i in range(N): if (vis[i] == False): continuousCol += 1 else: maxContinuousCol = max(maxContinuousCol, continuousCol) continuousCol = 0 maxContinuousCol = max( maxContinuousCol, continuousCol) # Condition to check if no P # continuous columns were # left unpainted if (maxContinuousCol < P): return 1 # return 0 if there are P # continuous columns are # left unpainted return 0 # Condition to check if No # further cells can be # painted, so return 0 if (col >= N): return 0 # if already calculated the value # return the val instead # of calculating again if (dp[col][prevCol][painted][prev] != -1): return dp[col][prevCol][painted][prev] res = 0 # Previous column was not painted if (prev == 0): # Column is painted so, # make vis[col]=true vis[col] = True res += ((helper( col + 1, 0, painted + 1, 1, N, P, K)) % mod) res += ((helper( col + 1, 0, painted + 1, 2, N, P, K)) % mod) res += ((helper( col + 1, 0, painted + 1, 3, N, P, K)) % mod) # Condition to check if the number # of cells to be painted is equal # to or more than 2, then we can # paint first and third row if (painted + 2 <= K): res += ((helper( col + 1, 0, painted + 2, 4, N, P, K)) % mod) vis[col] = False # Condition to check if number of # previous continuous columns left # unpainted is less than P if (prevCol + 1 < P): res += ((helper( col + 1, prevCol + 1, painted, 0, N, P, K)) % mod) # Condition to check if first row # was painted in previous column elif (prev == 1): vis[col] = True res += ((helper( col + 1, 0, painted + 1, 2, N, P, K)) % mod) res += ((helper( col + 1, 0, painted + 1, 3, N, P, K)) % mod) vis[col] = False if (prevCol + 1 < P): res += ((helper( col + 1, prevCol + 1, painted, 0, N, P, K)) % mod) # Condition to check if second row # was painted in previous column elif (prev == 2): vis[col] = True res += ((helper( col + 1, 0, painted + 1, 1, N, P, K)) % mod) res += ((helper( col + 1, 0, painted + 1, 3, N, P, K)) % mod) # Condition to check if the number # of cells to be painted is equal to # or more than 2, then we can # paint first and third row if (painted + 2 <= K): res += ((helper( col + 1, 0, painted + 2, 4, N, P, K)) % mod) vis[col] = False if (prevCol + 1 < P): res += ((helper( col + 1, prevCol + 1, painted, 0, N, P, K)) % mod) # Condition to check if third row # was painted in previous column elif (prev == 3): vis[col] = True res += ((helper( col + 1, 0, painted + 1, 1, N, P, K)) % mod) res += ((helper( col + 1, 0, painted + 1, 2, N, P, K)) % mod) vis[col] = False if (prevCol + 1 < P): res += ((helper( col + 1, prevCol + 1, painted, 0, N, P, K)) % mod) # Condition to check if first and # third row were painted # in previous column else: vis[col] = True res += ((helper( col + 1, 0, painted + 1, 2, N, P, K)) % mod) vis[col] = False if (prevCol + 1 < P): res += ((helper( col + 1, prevCol + 1, painted, 0, N, P, K)) % mod) # Memoize the data and return the # Computed value dp[col][prevCol][painted][prev] = res % mod return dp[col][prevCol][painted][prev] # Function to find the number of # ways to paint 3 x N grid def solve(n, p, k): # Set all values # of dp to -1; global dp # Set all values of Visited # array to false global vis return helper(0, 0, 0, 0, n, p, k) # Driver Code if __name__ == "__main__": N = 2 K = 2 P = 2 print(int(solve(N, P, K))) # This code is contributed by ukasp.
C#
// C# implementation to find the
// number of ways to paint K cells of
// 3 x N grid such that No two adjacent
// cells are painted
using System;
class GFG{
static int mod = (int)(1e9 + 7);
static readonly int MAX = 301;
static readonly int MAXP = 3;
static readonly int MAXK = 600;
static readonly int MAXPREV = 4;
static int [,,,]dp = new int[MAX, MAXP + 1,
MAXK, MAXPREV + 1];
// Visited array to keep track
// of which columns were painted
static bool []vis = new bool[MAX];
// Recursive Function to compute the
// number of ways to paint the K cells
// of the 3 x N grid
static int helper(int col, int prevCol,
int painted, int prev,
int N, int P, int K)
{
// Condition to check if total
// cells painted are K
if (painted >= K)
{
int continuousCol = 0;
int maxContinuousCol = 0;
// Check if any P continuous
// columns were left unpainted
for(int i = 0; i < N; i++)
{
if (vis[i] == false)
continuousCol++;
else
{
maxContinuousCol = Math.Max(
maxContinuousCol,
continuousCol);
continuousCol = 0;
}
}
maxContinuousCol = Math.Max(
maxContinuousCol,
continuousCol);
// Condition to check if no P
// continuous columns were
// left unpainted
if (maxContinuousCol < P)
return 1;
// return 0 if there are P
// continuous columns are
// left unpainted
return 0;
}
// Condition to check if No
// further cells can be
// painted, so return 0
if (col >= N)
return 0;
// If already calculated the value
// return the val instead
// of calculating again
if (dp[col, prevCol, painted, prev] != -1)
return dp[col, prevCol, painted, prev];
int res = 0;
// Previous column was not painted
if (prev == 0)
{
// Column is painted so,
// make vis[col]=true
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal
// to or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
// Condition to check if number of
// previous continuous columns left
// unpainted is less than P
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first row
// was painted in previous column
else if (prev == 1)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if second row
// was painted in previous column
else if (prev == 2)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal to
// or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if third row
// was painted in previous column
else if (prev == 3)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first and
// third row were painted
// in previous column
else
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Memoize the data and return
// the computed value
return dp[col, prevCol, painted, prev] = res % mod;
}
// Function to find the number of
// ways to paint 3 x N grid
static int solve(int n, int p, int K)
{
// Set all values
// of dp to -1;
for(int i = 0; i < MAX; i++)
for(int j = 0; j < MAXP + 1; j++)
for(int k = 0; k < MAXK; k++)
for(int l = 0; l < MAXPREV + 1; l++)
dp[i, j, k, l] = -1;
// Set all values of Visited
// array to false
for(int i = 0; i < vis.Length; i++)
vis[i] = false;
return helper(0, 0, 0, 0, n, p, K);
}
// Driver Code
public static void Main(String[] args)
{
int N = 2, K = 2, P = 2;
Console.Write(solve(N, P, K) + "\n");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript implementation to find the
// number of ways to paint K cells of
// 3 x N grid such that No two adjacent
// cells are painted
let mod = (1e9 + 7);
let MAX = 301;
let MAXP = 3;
let MAXK = 600;
let MAXPREV = 4;
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAXP + 1);
for(let j = 0; j < (MAXP + 1); j++)
{
dp[i][j] = new Array(MAXK);
for(let k = 0; k < MAXK; k++)
{
dp[i][j][k] = new Array(MAXPREV + 1);
for(let l = 0; l < (MAXPREV + 1); l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
// Visited array to keep track
// of which columns were painted
let vis = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
vis[i] = false;
}
// Recursive Function to compute the
// number of ways to paint the K cells
// of the 3 x N grid
function helper(col, prevCol, painted, prev, N, P, K)
{
// Condition to check if total
// cells painted are K
if (painted >= K)
{
let continuousCol = 0;
let maxContinuousCol = 0;
// Check if any P continuous
// columns were left unpainted
for(let i = 0; i < N; i++)
{
if (vis[i] == false)
continuousCol++;
else
{
maxContinuousCol = Math.max(
maxContinuousCol,
continuousCol);
continuousCol = 0;
}
}
maxContinuousCol = Math.max(
maxContinuousCol,
continuousCol);
// Condition to check if no P
// continuous columns were
// left unpainted
if (maxContinuousCol < P)
return 1;
// return 0 if there are P
// continuous columns are
// left unpainted
return 0;
}
// Condition to check if No
// further cells can be
// painted, so return 0
if (col >= N)
return 0;
// If already calculated the value
// return the val instead
// of calculating again
if (dp[col][prevCol][painted][prev] != -1)
return dp[col][prevCol][painted][prev];
let res = 0;
// Previous column was not painted
if (prev == 0)
{
// Column is painted so,
// make vis[col]=true
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal
// to or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
// Condition to check if number of
// previous continuous columns left
// unpainted is less than P
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first row
// was painted in previous column
else if (prev == 1)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if second row
// was painted in previous column
else if (prev == 2)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
3, N, P, K)) % mod;
// Condition to check if the number
// of cells to be painted is equal to
// or more than 2, then we can
// paint first and third row
if (painted + 2 <= K)
{
res += (helper(col + 1, 0,
painted + 2,
4, N, P, K)) % mod;
}
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if third row
// was painted in previous column
else if (prev == 3)
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
1, N, P, K)) % mod;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Condition to check if first and
// third row were painted
// in previous column
else
{
vis[col] = true;
res += (helper(col + 1, 0,
painted + 1,
2, N, P, K)) % mod;
vis[col] = false;
if (prevCol + 1 < P)
{
res += (helper(col + 1,
prevCol + 1,
painted, 0,
N, P, K)) % mod;
}
}
// Memoize the data and return
// the computed value
return dp[col][prevCol][painted][prev] = res % mod;
}
// Function to find the number of
// ways to paint 3 x N grid
function solve(n,p,k)
{
return helper(0, 0, 0, 0, n, p, K);
}
// Driver Code
let N = 2, K = 2, P = 2;
document.write(solve(N, P, K) + "<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8
Publicación traducida automáticamente
Artículo escrito por vithalnakod y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA