Number of ways to make exactly C components in a 2 * N matrix | C ++ 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 ; Function to find the number of ways to make exactly C components in a 2 * N matrix ; if No of components at any stage exceeds the given number then base case ; Condition to check if already visited ; if not visited previously ; At the first column ; color { white , white } or { black , black } ; Color { white , black } or { black , white } ; If previous both rows have same color ; Fill with { same , same } and { white , black } and { black , white } ; Fill with same without increase in component as it has been counted previously ; When previous rows had { white , black } ; When previous rows had { black , white } ; Memoization ; Driver Code ; Initially at first column with 0 components
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n , k ; int dp [ 1024 ] [ 2048 ] [ 2 ] [ 2 ] ; int Ways ( int col , int comp , int row1 , int row2 ) { if ( comp > k ) return 0 ; if ( col > n ) { if ( comp == k ) return 1 ; else return 0 ; } if ( dp [ col ] [ comp ] [ row1 ] [ row2 ] != -1 ) return dp [ col ] [ comp ] [ row1 ] [ row2 ] ; else { int ans = 0 ; if ( col == 1 ) { ans = ( ans + Ways ( col + 1 , comp + 1 , 0 , 0 ) + Ways ( col + 1 , comp + 1 , 1 , 1 ) ) ; ans = ( ans + Ways ( col + 1 , comp + 2 , 0 , 1 ) + Ways ( col + 1 , comp + 2 , 1 , 0 ) ) ; } else { if ( ( row1 && row2 ) || ( ! row1 && ! row2 ) ) { ans = ( ( ( ans + Ways ( col + 1 , comp + 1 , 0 , 0 ) ) + Ways ( col + 1 , comp + 1 , 1 , 0 ) ) + Ways ( col + 1 , comp + 1 , 0 , 1 ) ) ; ans = ( ans + Ways ( col + 1 , comp , 1 , 1 ) ) ; } 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 ) ) ; } 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 ) ) ; } } return dp [ col ] [ comp ] [ row1 ] [ row2 ] = ans ; } } signed main ( ) { n = 2 ; k = 1 ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << Ways ( 1 , 0 , 0 , 0 ) ; return 0 ; }