Count unique paths is a matrix whose product of elements contains odd number of divisors | C ++ program for the above approach ; Stores the results ; Count of unique product paths ; Function to check whether number is perfect square or not ; If square root is an integer ; Function to calculate and store all the paths product in vector ; Store the value a [ 0 ] [ 0 ] ; Initialize first row of dp ; Find prefix product ; Initialize first column of dp ; Find the prefix product ; Iterate over range ( 1 , 1 ) to ( N , M ) ; Copy dp [ i - 1 ] [ j ] in top [ ] ; Copy dp [ i ] [ j - 1 ] into left [ ] ; Compute the values of current state and store it in curr [ ] ; Find the product of a [ i ] [ j ] with elements at top [ ] ; Find the product of a [ i ] [ j ] with elements at left [ ] ; Update the current state ; Traverse dp [ m - 1 ] [ n - 1 ] ; Check if perfect square ; Driver Code ; Given matrix mat [ ] [ ] ; Function Call ; Print the final count
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < vector < int > > > dp ( 105 , vector < vector < int > > ( 105 ) ) ; int countPaths = 0 ; bool isPerfectSquare ( int n ) { long double sr = sqrt ( n ) ; return ( ( sr - floor ( sr ) ) == 0 ) ; } void countUniquePaths ( int a [ ] [ 105 ] , int m , int n , int ans ) { dp [ 0 ] [ 0 ] . push_back ( a [ 0 ] [ 0 ] ) ; for ( int i = 1 ; i < m ; i ++ ) { a [ i ] [ 0 ] *= a [ i - 1 ] [ 0 ] ; dp [ i ] [ 0 ] . push_back ( a [ i ] [ 0 ] ) ; } for ( int i = 1 ; i < n ; i ++ ) { a [ 0 ] [ i ] *= a [ 0 ] [ i - 1 ] ; dp [ 0 ] [ i ] . push_back ( a [ 0 ] [ i ] ) ; } for ( int i = 1 ; i < m ; i ++ ) { for ( int j = 1 ; j < n ; j ++ ) { vector < int > top = dp [ i - 1 ] [ j ] ; vector < int > left = dp [ i ] [ j - 1 ] ; vector < int > curr ; for ( int k = 0 ; k < top . size ( ) ; k ++ ) { curr . push_back ( top [ k ] * a [ i ] [ j ] ) ; } for ( int k = 0 ; k < left . size ( ) ; k ++ ) { curr . push_back ( left [ k ] * a [ i ] [ j ] ) ; } dp [ i ] [ j ] = curr ; } } for ( auto i : dp [ m - 1 ] [ n - 1 ] ) { if ( isPerfectSquare ( i ) ) { countPaths ++ ; } } } int main ( ) { int M = 3 , N = 4 ; int mat [ M ] [ 105 ] = { { 1 , 2 , 3 , 1 } , { 3 , 1 , 2 , 4 } , { 2 , 3 , 1 , 1 } } ; countUniquePaths ( mat , M , N , 1 ) ; cout << countPaths ; return 0 ; }