Problem Statement

Given a 3 x A board, find the number of ways to color it using at most 4 colors such that no 2 adjacent boxes have same color.

Diagonal neighbors are not treated as adjacent boxes.

Return the ways modulo 109 + 7 as the answer grows quickly.

Input Format:

The first and the only argument contains an integer, A.

Output Format:

Return an integer representing the number of ways to color the board.

Constraints:

1 <= A < 100000

Examples:

`Input 1: A = 1

Output 1: 36

Input 2: A = 2

Output 2: 588`

Problem Link

Ways to color a 3xN Board - InterviewBit

Reference Video

https://www.youtube.com/watch?v=wInXbAHi72g

Code

#define mod 1000000007
struct triplet
{
    int x;
    int y;
    int z;
};
vector<triplet> trip;

void formTriplets()//creating the trip vector whose final size will be 36
{
    trip.clear();
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<4;k++)
            {
                if(i!=j&&j!=k)
                trip.push_back({i,j,k});
            }
        }
    }
}

bool isCompatible(triplet &t1,triplet &t2)
{
    if(t1.x==t2.x || t1.y==t2.y || t1.z==t2.z)
    return 0;
    
    return 1;
}

int Solution::solve(int A) {
    
    formTriplets();
    
    int dp[4][4][4][A+1];
    
    for(int i=1;i<=A;i++)
    {
        for(int j=0;j<36;j++)
        {
            if(i==1)// No. of ways to fill a single triplet with jth set of valid
            // color combination will be equal to 1
            dp[trip[j].x][trip[j].y][trip[j].z][i] = 1;
            
            else
            {
                int temp = 0;
                
                for(int k=0;k<36;k++)
                {
                    if(isCompatible(trip[j],trip[k]))
                    {
                        temp = (temp + dp[trip[k].x][trip[k].y][trip[k].z][i-1]%mod)%mod;
                    }
                }
                dp[trip[j].x][trip[j].y][trip[j].z][i] = temp;
            }
        }
    }
    long long int ans = 0;
    
    for(int i=0;i<trip.size();i++)
    ans = (ans + dp[trip[i].x][trip[i].y][trip[i].z][A]%mod)%mod;
    
    return ans;
}