Count unique paths is a matrix whose product of elements contains odd number of divisors | Python3 program for the above approach ; Function to calculate and store all the paths product in vector ; Base Case ; If reaches the bottom right corner and product is a perfect square ; Find square root ; If square root is an integer ; Move towards down in the matrix ; Move towards right in the matrix ; Driver Code ; Given matrix mat ; Function call
import math NEW_LINE countPaths = 0 ; NEW_LINE def CountUniquePaths ( a , i , j , m , n , ans ) : NEW_LINE INDENT if ( i >= m or j >= n ) : NEW_LINE INDENT return ; NEW_LINE DEDENT global countPaths ; NEW_LINE if ( i == m - 1 and j == n - 1 ) : NEW_LINE INDENT sr = math . sqrt ( ans * a [ i ] [ j ] ) ; NEW_LINE if ( ( sr - math . floor ( sr ) ) == 0 ) : NEW_LINE INDENT countPaths += 1 ; NEW_LINE DEDENT DEDENT CountUniquePaths ( a , i + 1 , j , m , n , ans * a [ i ] [ j ] ) ; NEW_LINE CountUniquePaths ( a , i , j + 1 , m , n , ans * a [ i ] [ j ] ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT M = 3 ; N = 2 ; NEW_LINE mat = [ [ 1 , 1 ] , [ 3 , 1 ] , [ 3 , 1 ] ] ; NEW_LINE CountUniquePaths ( mat , 0 , 0 , M , N , 1 ) ; NEW_LINE print ( countPaths ) ; NEW_LINE DEDENT