Count unique paths is a matrix whose product of elements contains odd number of divisors | Python3 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
from math import sqrt , floor NEW_LINE dp = [ [ [ ] for j in range ( 105 ) ] for k in range ( 105 ) ] NEW_LINE countPaths = 0 NEW_LINE def isPerfectSquare ( n ) : NEW_LINE INDENT sr = sqrt ( n ) NEW_LINE return ( ( sr - floor ( sr ) ) == 0 ) NEW_LINE DEDENT def countUniquePaths ( a , m , n , ans ) : NEW_LINE INDENT global dp NEW_LINE global countPaths NEW_LINE dp [ 0 ] [ 0 ] . append ( a [ 0 ] [ 0 ] ) NEW_LINE for i in range ( 1 , m ) : NEW_LINE INDENT a [ i ] [ 0 ] *= a [ i - 1 ] [ 0 ] NEW_LINE dp [ i ] [ 0 ] . append ( a [ i ] [ 0 ] ) NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT a [ 0 ] [ i ] *= a [ 0 ] [ i - 1 ] NEW_LINE dp [ 0 ] [ i ] . append ( a [ 0 ] [ i ] ) NEW_LINE DEDENT for i in range ( 1 , m ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT top = dp [ i - 1 ] [ j ] NEW_LINE left = dp [ i ] [ j - 1 ] NEW_LINE curr = [ ] NEW_LINE for k in range ( len ( top ) ) : NEW_LINE INDENT curr . append ( top [ k ] * a [ i ] [ j ] ) NEW_LINE DEDENT for k in range ( len ( left ) ) : NEW_LINE INDENT curr . append ( left [ k ] * a [ i ] [ j ] ) NEW_LINE DEDENT dp [ i ] [ j ] = curr NEW_LINE DEDENT DEDENT for i in dp [ m - 1 ] [ n - 1 ] : NEW_LINE INDENT if ( isPerfectSquare ( i ) ) : NEW_LINE INDENT countPaths += 1 NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT M = 3 NEW_LINE N = 4 NEW_LINE mat = [ [ 1 , 2 , 3 , 1 ] , [ 3 , 1 , 2 , 4 ] , [ 2 , 3 , 1 , 1 ] ] NEW_LINE countUniquePaths ( mat , M , N , 1 ) NEW_LINE print ( countPaths ) NEW_LINE DEDENT