Count unique paths is a matrix whose product of elements contains odd number of divisors | Java 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 java . io . * ; import java . util . * ; import java . lang . * ; class GFG { static int countPaths = 0 ; static void CountUniquePaths ( int [ ] [ ] a , int i , int j , int m , int n , int ans ) { if ( i >= m j >= n ) return ; if ( i == m - 1 && j == n - 1 ) { double sr = Math . sqrt ( ans * a [ i ] [ j ] ) ; if ( ( sr - Math . floor ( sr ) ) == 0 ) countPaths ++ ; } CountUniquePaths ( a , i + 1 , j , m , n , ans * a [ i ] [ j ] ) ; CountUniquePaths ( a , i , j + 1 , m , n , ans * a [ i ] [ j ] ) ; } public static void main ( String [ ] args ) { int M = 3 , N = 2 ; int [ ] [ ] mat = { { 1 , 1 } , { 3 , 1 } , { 3 , 1 } } ; CountUniquePaths ( mat , 0 , 0 , M , N , 1 ) ; System . out . println ( countPaths ) ; } }