Count unique paths is a matrix whose product of elements contains odd number of divisors | 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
let dp = [ ] ; let countPaths = 0 ; function isPerfectSquare ( n ) { let sr = Math . sqrt ( n ) ; return ( ( sr - Math . floor ( sr ) ) == 0 ) ; } function countUniquePaths ( a , m , n , ans ) { dp [ 0 ] [ 0 ] . push ( a [ 0 ] [ 0 ] ) ; for ( let i = 1 ; i < m ; i ++ ) { a [ i ] [ 0 ] *= a [ i - 1 ] [ 0 ] ; dp [ i ] [ 0 ] . push ( a [ i ] [ 0 ] ) ; } for ( let i = 1 ; i < n ; i ++ ) { a [ 0 ] [ i ] *= a [ 0 ] [ i - 1 ] ; dp [ 0 ] [ i ] . push ( a [ 0 ] [ i ] ) ; } for ( let i = 1 ; i < m ; i ++ ) { for ( let j = 1 ; j < n ; j ++ ) { let top = dp [ i - 1 ] [ j ] ; let left = dp [ i ] [ j - 1 ] ; let curr = [ ] ; for ( let k = 0 ; k < top . length ; k ++ ) { curr . push ( top [ k ] * a [ i ] [ j ] ) ; } for ( let k = 0 ; k < left . length ; k ++ ) { curr . push ( left [ k ] * a [ i ] [ j ] ) ; } dp [ i ] [ j ] = curr ; } } for ( let i = 0 ; i < dp [ m - 1 ] [ n - 1 ] . length ; i ++ ) { if ( isPerfectSquare ( dp [ m - 1 ] [ n - 1 ] [ i ] ) ) { countPaths ++ ; } } } let M = 3 , N = 4 ; let mat = [ [ 1 , 2 , 3 , 1 ] , [ 3 , 1 , 2 , 4 ] , [ 2 , 3 , 1 , 1 ] ] ; for ( let i = 0 ; i < 105 ; i ++ ) { dp . push ( [ ] ) ; for ( let j = 0 ; j < 105 ; j ++ ) dp [ i ] . push ( [ ] ) ; } countUniquePaths ( mat , M , N , 1 ) ; document . write ( countPaths ) ;