Count unique paths is a matrix whose product of elements contains odd number of divisors | Java 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
import java . util . * ; class GFG { static ArrayList < ArrayList < ArrayList < Integer > > > dp ; static int countPaths = 0 ; static boolean isPerfectSquare ( int n ) { double sr = Math . sqrt ( n ) ; return ( ( sr - Math . floor ( sr ) ) == 0 ) ; } static void countUniquePaths ( int a [ ] [ ] , int m , int n , int ans ) { dp . get ( 0 ) . get ( 0 ) . add ( a [ 0 ] [ 0 ] ) ; for ( int i = 1 ; i < m ; i ++ ) { a [ i ] [ 0 ] *= a [ i - 1 ] [ 0 ] ; dp . get ( i ) . get ( 0 ) . add ( a [ i ] [ 0 ] ) ; } for ( int i = 1 ; i < n ; i ++ ) { a [ 0 ] [ i ] *= a [ 0 ] [ i - 1 ] ; dp . get ( 0 ) . get ( i ) . add ( a [ 0 ] [ i ] ) ; } for ( int i = 1 ; i < m ; i ++ ) { for ( int j = 1 ; j < n ; j ++ ) { ArrayList < Integer > top = dp . get ( i - 1 ) . get ( j ) ; ArrayList < Integer > left = dp . get ( i ) . get ( j - 1 ) ; ArrayList < Integer > curr = new ArrayList < > ( ) ; for ( int k = 0 ; k < top . size ( ) ; k ++ ) { curr . add ( top . get ( k ) * a [ i ] [ j ] ) ; } for ( int k = 0 ; k < left . size ( ) ; k ++ ) { curr . add ( left . get ( k ) * a [ i ] [ j ] ) ; } dp . get ( i ) . set ( j , curr ) ; } } for ( Integer i : dp . get ( m - 1 ) . get ( n - 1 ) ) { if ( isPerfectSquare ( i ) ) { countPaths ++ ; } } } public static void main ( String [ ] args ) { int M = 3 , N = 4 ; int mat [ ] [ ] = { { 1 , 2 , 3 , 1 } , { 3 , 1 , 2 , 4 } , { 2 , 3 , 1 , 1 } } ; dp = new ArrayList < > ( ) ; for ( int i = 0 ; i < 105 ; i ++ ) { dp . add ( new ArrayList < > ( ) ) ; for ( int j = 0 ; j < 105 ; j ++ ) dp . get ( i ) . add ( new ArrayList < Integer > ( ) ) ; } countUniquePaths ( mat , M , N , 1 ) ; System . out . println ( countPaths ) ; } }